自然な証明

ウィキペディア

自然な証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/06/07 18:16 UTC 版)

計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。

ウィキペディア小見出し辞書

自然な証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/16 08:14 UTC 版)

「P≠NP予想」の記事における「自然な証明」の解説

詳細は「自然な証明」を参照 1980年代に入り、集合論的手法ではない回路計算量に着目する新しい証明手法が開発された。これは今日「自然な証明」と呼ばれるもので、AC0≠NC1（Furst, Saxe & Sipser (1984)）やmP/poly≠NP（Razborov (1985))などの成果を挙げた。この手法からP≠NPを見る場合は、Pを包含するクラスP/poly（英語版）に着目してP/poly≠NPを証明することが問題となる（そこから直ちにP≠NPが従う）。 ところが、当初の期待にも関わらず、P/poly≠NPに向けた進展はぱったり止まってしまい、やがて研究者の間で何か原因があるのではないかと議論されるようになった。そんな中、Razborov & Rudich (1997)はその原因を突き止め、次のことを示した。 素因数分解の困難性を仮定すると、自然な証明ではP/poly≠NPを証明できない 「自然な証明」は名前の通り自然な発想に基づく証明戦略であり、それまで得られた複雑性クラスの分離に関する殆ど全ての証明で利用されていた。ところが、そうした証明手法ではP≠NPを原理的に証明できないことが判明したのである。RazborovとRudichはこの成果により2007年のゲーデル賞を受賞した。但し彼らが定義した「自然な証明」には幾つか技術的な条件があることから、この条件を巧妙に回避することで障害を乗り越えようとする研究方向も存在する。