Truth vs. Proof in Computational Complexity
Boaz Barak · 2012
Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the P vs NP problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could remain agnostic, saying that we simply don’t know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed [Aar10] that in other sciences P 6 = NP would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won’t go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles. But what other methods can we use to get evidence for questions in computational complexity? After all, it seems completely hopeless to experimentally verify even a non-asymptotic statement such as “There is no circuit of size 2100 that can solve 3SAT on 10, 000 variables”. There is in some sense only one tool us scientists can use to predict the answer to open questions, and this is Occam’s Razor. That is, if we want