自然な証明
(Natural proof から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/06/07 18:16 UTC 版)
計算複雑性理論において、自然な証明（英：natural proof）とは、ある複雑性クラスが他の複雑性クラスとは異なることを示すための証明手法の一種である。これに則る証明はある意味で「自然」だが、擬似乱数生成器の存在を仮定すると、そのような方法ではP≠NP予想を解決不可能であることが言える。なお「擬似乱数生成器が存在する」という主張は広く正しいと信じられている予想である。
- ^ “ACM-SIGACT 2007 Godel Prize” (2007年). 2017年6月7日閲覧。
- ^ Razborov, A. A.; Rudich, S. (1997). “Natural proofs”. Journal of Computer and System Sciences 55: 24-35. doi:10.1006/jcss.1997.1494. (Draft)
- ^ https://complexityzoo.uwaterloo.ca/Complexity_Zoo:T#tc0
- ^ Regan, K. (2002-10). “Understanding the Mulmuley-Sohoni Approach to P vs. NP” (PDF). Bulletin of the European Association for Theoretical Computer Science 78: 86-97.
[続きの解説]
「自然な証明」の続きの解説一覧
- 1 自然な証明とは
- 2 自然な証明の概要
- 3 その他
- Natural proofのページへのリンク
