半代数的証明,IPS下界,およびτ予想:自然数は負か?【JST・京大機械翻訳】

Alekseev Yaroslav; Grigoriev Dima; Hirsch Edward A.; Tzameret Iddo

文献

J-GLOBAL ID：202002241496840006 整理番号：20A2077909

半代数的証明,IPS下界,およびτ予想:自然数は負か?【JST・京大機械翻訳】

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A2077909&from=J-GLOBAL&jstjournalNo=D0698C") }}

著者 (4件)： , , ,
資料名：
号： STOC 2020 ページ： 54-67 発行年： 2020年
JST資料番号： D0698C 資料種別：会議録 (C)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

バイナリで書かれた自然数が負でないという簡単な部分集合和インスタンスである二値値原理を導入し,それを証明と代数的複雑性における中心問題に関連づける。この事例の理想的Proof System(IPS)リフテーションサイズに関する条件付き超多項式下限を,ShubとSmaleによる良く知られた仮説に基づいて,計算要因の硬度について証明し,そこでは,IPSがGrocowとPitassi(2011)によって導入された強い代数証明システムである。逆に,著者らは,このインスタンスの短いIPSリフテーションが,十分に強い代数的および半代数的証明システムの間のギャップを埋めることを示した。著者等の結果は,Forbesら(2016)に導入されたパラダイムをフルフレッジしたIPSに拡張し,IPSのサブシステムに対する下限は,制限代数回路下限を用いて得られ,二値値原理が,十分に強いシステムに対して,代数的推論に対する半代数の利点を捉えることを実証した。特に,条件付きIPS下限:Shub-Smale仮説(1995)は,Boolean x_iに対する不充足線形方程式Σ_i=1n2i-1x_i=-1として定義される有理上の二値値原理のIPS再推定のサイズに関する超多項式下限を暗示するものである。”Shub-Smale仮説(195)は,非充足線形方程式Σ_i=1n2i-1x_i=-1として定義される。さらに,関連するτ-コンジェクチャー(195)は,合理的関数のリング上の二値値原理のバリアントのIPS再推定のサイズに関する超多項式下限を意味する。IPSまたはFregeのような明らかに非常に弱い命題証明システムに対して,事前の条件付き下限は知られていない。Algebraic対半代数証明は,任意の既知の半代数証明システムを完全にシミュレートする任意の代数証明システムに対して必要であり,また,十分に十分な代数証明システムにとっても十分である。特に,理想的な証明システムの半代数的アナログであるCone Proof System(CPS)の下で,すべての既知の半代数証明システム(および他の既知のコンクリート命題証明システム)をシミュレーションする非常に強い証明システムを導入し,CPSは,代数的回路として平方和証明(および拡張)を表現することによって,実物上の多項式同等性と不等式の収集の不満足性を確立した。IPSは,ZとQの両方にわたって,2値原理(0/1解を持たない方程式系の言語に対して)の多項式サイズリフテーションをCPS iff IPSに多項式的に等価であることを証明する。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】

著者キーワード (6件)： , , , , ,

符号理論

, , ,

前のページに戻る