近似法とP対NP問題【JST・京大機械翻訳】

Blum Norbert

プレプリント

J-GLOBAL ID：202202206075145138 整理番号：22P0041697

近似法とP対NP問題【JST・京大機械翻訳】

On the Approximation Method and the P versus NP Problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2017年08月11日プレプリントサーバーでの情報更新日： 2020年06月15日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

最初に,著者らは,「自然証明」が,Boole複雑性を用いてPot=NPを証明するための障壁でないという理由を与えた。次に,NPにおける適切なBoole関数の非単調複雑性に対する超多項式下限を証明し,これがなぜ可能でないかを理解するために,その拡張に対する近似法を検討した。近似法だけでは,任意の関数f∈B_nに対する超線形下限を証明できないといういくつかの証拠を与えた。さらに,非単調の下限とBoole関数の単調複雑性を証明する方法に関する概観を与えた。最後に,P対NP問題に関する研究をいかに進めるか,またNPにおけるBoole関数の非単調複雑性に対する超線形下限を証明できる個人意見を与えた。【JST・京大機械翻訳】

, , , , , ,
, 【Automatic Indexing@JST】

計算理論

前のページに戻る