The Bactra Review   Labyrinths of Reason

---

A more precise statement of the case is as follows. If we have a solution, we can check that it works in polynomial time. So an oracle which always gave us the right answer, which we just checked out of caution, would solve the problem in polynomial time: such problems are called ``NP,'' ``non-deterministic polynomial.'' (``Non-deterministic'' sounds better to computer scientists than ``magical.'') Not having such oracles handy, we have to actually generate the solution algorithmically, and there are no known algorithms which take less than exponential time. (There is also no proof that such algorithms don't exist; whether P=NP is an open problem.)