文献

J-GLOBAL ID：202002283889429388   整理番号：20A2461414

モジュロ-q議論の複雑性とChevalley-Warning定理【JST・京大機械翻訳】

On the complexity of modulo-q arguments and the chevalley-warning theorem

著者 (4件)： Goos Mika (Stanford University) ,  Kamath Pritish (Toyota Technological Institute at Chicago) ,  Sotiraki Katerina (Massachusetts Institute of Technology) ,  Zampetakis Manolis (Massachusetts Institute of Technology)
資料名： ACM Proceedings  (ACM Proceedings)
号： CCC ’20  ページ： 1-42  発行年： 2020年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Papadimitriou(JCSS 1994)により導入されたよく知られた多項式パリティ議論クラスPPAのモジュロ-qアナログとして定義される探索問題クラスPPA_qを研究した。最初の結果は,このクラスがプライムpのPPA_pに関して特性化できることを示した。主な結果は,Che谷-Warning定理に関連した探索問題の明示的バージョンが,プライムpのPPA_pに対して完全であることを確立することである。この問題は,入力の一部として回路を明示的に含まないという点で自然である。p≧3のとき,PPA_pに対する最初のそのような完全な問題であり,Che谷-Warning定理とよく研究された短い整数解問題の間の接続を議論し,PPA_qの構造特性を調べた。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *多項式 ,  探索問題 ,  アナログ系 ,  キャラクタリゼーション ,  構造特性
準シソーラス用語： 複雑性 , 【Automatic Indexing@JST】

著者キーワード (3件)： Chevalley-warning定理 ,  modulo-qargument ,  全NP探索問題

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 議論 ,  複雑性 ,  定理