P=?NP問題の証明【JST・京大機械翻訳】

Wan Changlin; Shi Zhongzhi

プレプリント

J-GLOBAL ID：202202206028622432 整理番号：22P0034857

P=?NP問題の証明【JST・京大機械翻訳】

A Proof for P =? NP Problem

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

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

著者 (2件)： ,
資料名：
発行年： 2010年05月17日プレプリントサーバーでの情報更新日： 2020年07月01日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

P対NP問題は,現代の数学と理論的コンピュータ科学における重要な問題である。この問題に対して多くの証明が提案されてきた。本論文では,P対NP問題に対する理論的証明を提案した。この証明の中心的アイデアは,定義によって有効なTMの符号化ストリングを受け入れるTuringマシン(短TM)のための再帰的定義であり,TMの無限シーケンスを構築し,シーケンスがこれらのTMに基づくすべての有効なTMを含み,すべての可解言語を含むクラスDと結合と縮小オペレータを定義することを証明した。Dの融合の言語アップを構築することによって,P=UpとUp=NP,および結果P=NPを証明した。【JST・京大機械翻訳】

, , , , ,

計算理論

, ,

前のページに戻る