講演抄録/キーワード |
講演名 |
2016-06-24 13:45
多項式時間数え上げ階層の緩減算的還元のもとでの完全性について ○松原俊一(青学大) COMP2016-7 |
抄録 |
(和) |
多項式時間階層~は Meyer と Stockmeyer により発見された判定問題に関する階層であり,多くの研究がなされている.この階層の数え上げ問題版の一つである#・Π_0 ⊆ ... ⊆ ... #・Π_k ⊆ ... は,parsimonious 還元では完全問題が存在するが,多項式時間 1 Turing還元では階層が崩壊することが知られている.その一方で parsimonious還元は問題固有の性質に強く依存するため,問題の構造が大きく異なる場合,構成が困難なことも少なくない.すなわち数え上げ問題版の多項式時間階層は判定問題に比べ,多項式時間還元の種類への依存がより高いと言える.数え上げ問題において NP と対応付けられる #P は,多くの数え上げ問題を含み,完全問題も知られている.しかし #P に含まれないと予想され,ある仮定のもとではそれが証明されている問題も存在する.parsimonious 還元のもとでの #Σ_k SAT などである (k ≧ 2).Durand らは parsimonious 還元と多項式時間 1 還元の中間に位置する減算的還元を導入し,この還元のもとでの完全問題の存在を具体的に示している.本研究では緩減算的還元を導入し,この還元が数え上げ版の多項式時間階層の各レベルで閉じていることを示す. |
(英) |
The polynomial-time hierarchy was introduced by Meyer and Stockmeyer, which is a hierarchy on decision problems and has actively been researched. $#cdotPI_0^P subseteq cdots subseteq #cdotPi_k^P subseteq cdots$ has also been researched as one of counting problem versions of the polynomial-time hierarchy. The class of each level $k$ in this hierarchy contains complete problems under parsimonious reducibility while this hierarchy is known to be collapsed under polynomial-time $1$ Turing reductions. On the other hand, parsimonious reductions are difficult to construct for their weakness of power if the structures of two counting problems are quite different. That is, properties of the hierarchy on counting problems depends on which kind of reducibility we adopt. In this paper, we introduce relaxed subtractive reductions that have some intermediate power for the two reducibilities by extending the subtractive reducibility introduced by Durand et al. Moreover, we show the closure property under the new reduction. |
キーワード |
(和) |
多項式時間階層 / 数え上げ問題 / 相対化 / 多項式時間還元 / 計算複雑さ / / / |
(英) |
polynomial-time hierarchy / counting problems / relativization / polynomial-time reducibility / computational complexity / / / |
文献情報 |
信学技報, vol. 116, no. 116, COMP2016-7, pp. 9-12, 2016年6月. |
資料番号 |
COMP2016-7 |
発行日 |
2016-06-17 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-7 |