| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2016-06-24 - 2016-06-25 |
| 開催地（和） | 石川県教育会館 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-06-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 多項式時間数え上げ階層の緩減算的還元のもとでの完全性について |
| サブタイトル（和） | |
| タイトル（英） | On completeness of polynomial-time counting hierarchy under relaxed subtractive reductions |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 多項式時間階層 / polynomial-time hierarchy |
| キーワード(2)（和/英） | 数え上げ問題 / counting problems |
| キーワード(3)（和/英） | 相対化 / relativization |
| キーワード(4)（和/英） | 多項式時間還元 / polynomial-time reducibility |
| キーワード(5)（和/英） | 計算複雑さ / computational complexity |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 松原 俊一 / Shunichi Matsubara / マツバラ シュンイチ |
| 第1著者 所属（和/英） | 青山学院大学 (略称： 青学大) Aoyama Gakuin University (略称： Aoyama Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | / / |
| 第2著者 所属（和/英） | (略称： ) (略称： ) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-06-24 13:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-7 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.116 |
| ページ範囲 | pp.9-12 |
| ページ数 | 4 |
| 発行日 | 2016-06-17 (COMP) |
[研究会発表申込システムのトップページに戻る]