{"updated":"2025-01-19T17:09:32.866821+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00213446","sets":["6164:6165:6210:10734"]},"path":["10734"],"owner":"44499","recid":"213446","title":["一般化ぷよぷよのより強い計算困難性"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-11-06"},"_buckets":{"deposit":"fe51b0ac-1585-4116-904b-da0ec32be51a"},"_deposit":{"id":"213446","pid":{"type":"depid","value":"213446","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"一般化ぷよぷよのより強い計算困難性","author_link":["546181","546180","546184","546182","546183","546179"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"一般化ぷよぷよのより強い計算困難性"},{"subitem_title":"Stronger Hardness Results on Generalized Puyopuyo","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"ぷよぷよ","subitem_subject_scheme":"Other"},{"subitem_subject":"パズル計算量","subitem_subject_scheme":"Other"},{"subitem_subject":"NP 完全性","subitem_subject_scheme":"Other"},{"subitem_subject":"近似困難","subitem_subject_scheme":"Other"}]},"item_type_id":"18","publish_date":"2021-11-06","item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_18_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東北大学大学院情報科学研究科"},{"subitem_text_value":"九州大学大学院経済学研究院"},{"subitem_text_value":"名古屋大学大学院情報学研究科"}]},"item_18_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Information Science, Tohoku University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Economics, Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics, Nagoya University","subitem_text_language":"en"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/213446/files/IPSJ-GPWS2021025.pdf","label":"IPSJ-GPWS2021025.pdf"},"date":[{"dateType":"Available","dateValue":"2021-11-06"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-GPWS2021025.pdf","filesize":[{"value":"2.0 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"18"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"6c28c50f-c2e1-4dde-b546-9c848f664d16","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2021 by the Information Processing Society of Japan"}]},"item_18_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"江藤, 宏"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"木谷, 裕紀"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"小野, 廣隆"}],"nameIdentifiers":[{}]}]},"item_18_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Hiroshi, Eto","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hironori, Kiya","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_5794","resourcetype":"conference paper"}]},"item_18_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本研究では一般化ぷよぷよの計算複雑度について考える．対象とするのは盤面サイズ，色数に関して一般化した，オフライン型パズルとしてのぷよぷよである．本研究ではこの一般化ぷよぷよにおける 2つの問題を取り上げる．1 つは全消し判定であり，もう一つは連鎖数最大化である．前者に関してはぷよ 2色（おじゃまぷよあり）の設定であっても NP 完全であることが，後者に関してはぷよ 4 色（おじゃまぷよあり）の設定でも NP 困難であることが示されている．特に後者に関しては，詳細な証明は公開されていないがぷよ 3 色（おじゃまぷよあり）の設定で，あるいはぷよ 5 色（おじゃまぷよなし）でも NP 困難であることが指摘されている．本研究ではこれらの結果をいくつかの側面から強化する．我々の結果は以下のとおりである： (1) 連鎖数最大化はぷよ 3 色（おじゃまぷよなし）でも NP 困難，(2) P≠NP の仮定の下で， ぷよ 4 色（おじゃまぷよあり）の連鎖数最大化に対しては近似比の精度保証が入力の多項式以下となるような多項式時間近似アルゴリズムは存在しない， (3) 全消し判定はぷよ 4 色（おじゃまぷよなし）でも NP 完全である．","subitem_description_type":"Other"}]},"item_18_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper, we investigate the computational complexity of a generalized variant of Puyopuyo. The variant generalizes the size of the board and the number of colors but falling pairs of puyos are given in the offline manner. We focus on two problems of the generalized Puyopuyo; board clearing and maximizing chains. Both problems are already known to be NP-hard. More precisely, the former is NP-complete even for puyos of 2 colors with N-puyo setting, and the latter is NP-hard even for puyos of 4 colors with N-puyo setting. The latter result is mentioned to be improved to the setting of puyos of 3 colors with N-puyo and the setting of puyos of 5 colors without N-puyo, though the detail is not published. In this paper, we strengthen these results from several aspects. Our results are as follows: (1) The chain maximization is NP-hard even for the setting of puyos of 4 colors without N-puyo. (2) The chain maximization for puyos of 3 colors with N-puyo cannot be approximated within any polynomial factor in polynomial time, unless P=NP. (3) The board clearing is NP-complete even for the setting of puyos of 4 colors without N-puyo.","subitem_description_type":"Other"}]},"item_18_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"137","bibliographic_titles":[{"bibliographic_title":"ゲームプログラミングワークショップ2021論文集"}],"bibliographicPageStart":"130","bibliographicIssueDates":{"bibliographicIssueDate":"2021-11-06","bibliographicIssueDateType":"Issued"},"bibliographicVolumeNumber":"2021"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:14:19.433322+00:00","id":213446,"links":{}}