Many problems are known to be NP-complete. It is widely conjectured that NP-complete problems do not admit polynomial time algorithms. This section gives some formal details. Assuming that NP-complete problems do not admit polynomial time algorithms, the Cobham–Edmonds thesis entails that no NP-complete problem is feasibly solved.
Suppose we are given a set of boolean formulæ. One question we can ask is: is the set of formulæ satisfiable? But suppose someone insists that the set of formulæ is indeed satisfiable; they might, for instance, offer a satisfying assignment. There is then a second question: is the putative demonstration of satisfiability sound? (After all, the putative satisfying assignment might not in fact satisfy each of the formulæ.)
We write P for the class of problems where answering the first question takes polynomial time. Consider, for instance, the task of deciding whether a list is sorted, which can be done in linear time. We write NP for the class of problems where answering the second question takes polynomial time. The problem of satisfiability of boolean formulæ lies in NP, because it is possible to check that a satisfying assignment indeed satisfies a set of formulæ in time polynomial in the number of variables.
We don’t know. But there is some reason to think not.
To a first approximation, the standard argument for suspecting that is that there are many NP-complete problems and we haven’t found any polynomial-time algorithms for them, which would be a bit suspicious if they were secretly in P (Aaronson, P ?= NP: 3).
Therefore, it is widely conjectured that NP-complete (and NP-hard) problems simply aren’t in P. We will make this assumption for the remainder of this thesis.