| 講演名 | 2016-06-24 多項式時間数え上げ階層の緩減算的還元のもとでの完全性について 松原 俊一(青学大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 多項式時間階層~は 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 |
| 資料番号 | COMP2016-7 |
| 発行日 | 2016-06-17 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2016/6/24(から2日開催) |
| 開催地（和） | 石川県教育会館 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 伊藤 大雄(電通大) / 上原 隆平(北陸先端大) |
| 委員長氏名（英） | Hiroo Itoh(Univ. of Electro-Comm.) / Ryuhei Uehara(北陸先端大) |
| 副委員長氏名（和） | 宇野 裕之(阪府大) |
| 副委員長氏名（英） | Yuushi Uno(Osaka Pref. Univ.) |
| 幹事氏名（和） | 脊戸 和寿(成蹊大) / 斎藤 寿樹(神戸大) / 岡本 吉央(電通大) / 山内 由紀子(九大) / 内澤 啓(山形大) |
| 幹事氏名（英） | Kazuhisa Seto(Seikei Univ.) / Toshiki Saito(Kobe Univ.) / Yoshio Okamoto(電通大) / Yukiko Yamauchi(九大) / Kei Uchizawa(山形大) |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多項式時間数え上げ階層の緩減算的還元のもとでの完全性について |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| 第 1 著者 氏名（和/英） | 松原 俊一 / Shunichi Matsubara |
| 第 1 著者 所属（和/英） | 青山学院大学(略称：青学大) Aoyama Gakuin University(略称：Aoyama Gakuin Univ.) |
| 発表年月日 | 2016-06-24 |
| 資料番号 | COMP2016-7 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | COMP-116 |
| ページ範囲 | pp.9-12(COMP), |
| ページ数 | 4 |
| 発行日 | 2016-06-17 (COMP) |