トミサワ　マサキ   MASAKI TOMISAWA
  冨澤　眞樹
   所属   前橋工科大学  工学部 生命情報学科
   前橋工科大学  工学部 情報・生命工学群
   前橋工科大学大学院  工学研究科 環境・生命工学専攻（博士課程）
   前橋工科大学大学院  工学研究科 生命情報学専攻（修士課程）
   職種   准教授
受賞年月2021/03/03
国内外別 国内
授与機関名LA Symposium / EATCS (European Association for Theoretical Computer Science) Japan Chapter
受賞学術賞名第10回LA/EATCS-Japan学生発表論文賞
タイトルNP-completeness of k Generalized Lunar Lockout Variant
受賞者(グループ)加賀谷 光祐，冨澤 眞樹，遠山 宏明
受賞区分国内学会・会議・シンポジウム等の賞
概要スライディングパズル「Lunar Lockout」の一般化であるGeneralized Lunar Lockout VariantはPSPACE完全であることが知られている．本研究では，各駒の移動回数を高々k（定数）回に制限したGeneralized Lunar Lockout Variantが，k≧3のときNP完全であることを証明した．