Texonom
Texonom
/
Computing
Computing
/Computing Theory/Information Theory/Complexity Theory/P versus NP problem/
Natural proof
Search

Natural proof

Creator
Creator
Seonglae Cho
Created
Created
2023 Dec 2 10:54
Editor
Editor
Seonglae Cho
Edited
Edited
2023 Dec 2 11:0
Refs
Refs
Natural proofs are a certain kind of proof that establish that one complexity class differs from another.
 
 
 
 
 
Natural proof
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture on the existence of pseudorandom functions) that no such proof can possibly be used to solve the P vs. NP problem.
Natural proof
https://en.wikipedia.org/wiki/Natural_proof
 
 

Recommendations

Texonom
Texonom
/
Computing
Computing
/Computing Theory/Information Theory/Complexity Theory/P versus NP problem/
Natural proof
Copyright Seonglae Cho