講演抄録/キーワード |
講演名 |
2008-10-10 10:00
再構成問題の計算複雑さ ○伊藤健洋(東北大)・Erik D. Demaine・Nicholas J. A. Harvey(マサチューセッツ工科大)・Christos H. Papadimitriou(UC Berkeley)・Martha Sideri(AUEB)・上原隆平(北陸先端大)・宇野裕之(阪府大) COMP2008-36 |
抄録 |
(和) |
解の再構成問題とは,ある問題の2つの実行可能解が与えられたとき,一方の解から他方の解へ段階的に変形可能かどうか判定する問題である.ただし,変形の途中で得られる解の全ては,基の問題に対して実行可能でなければならない.本論文では,NP完全な問題から得られる再構成問題の多くがPSPACE完全であることを示す.また,いくつかの再構成問題に関しては,その最適化版の近似困難性も示す.その一方で,Pに含まれる問題の再構成問題のいくつかは,多項式時間で解けることも示す. |
(英) |
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. |
キーワード |
(和) |
PSPACE完全 / 近似困難性 / 再構成問題 / / / / / |
(英) |
approximability / PSPACE-complete / reconfiguration problem / / / / / |
文献情報 |
信学技報, vol. 108, no. 237, COMP2008-36, pp. 17-24, 2008年10月. |
資料番号 |
COMP2008-36 |
発行日 |
2008-10-03 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2008-36 |