did not try to forge *some* link, however tenuous, with the laws of physics as we currently understand them.

The Basics\[BASICS\]
====================

I will not say much about the original $\mathsf{P}$ versus $\mathsf{NP}$ question: only that the known heuristic algorithms for the 3SAT problem, such as backtrack, simulated annealing, GSAT, and survey propagation, can solve some instances quickly in practice, but are easily stumped by other instances; that the standard opinion is that $\mathsf{P}\neq\mathsf{NP}$ [@gasarch]; that proving this is correctly seen as one of the deepest problems in all of mathematics [@clay]; that no one has any idea where to begin [@feinstein]; and that we have a pretty sophisticated idea of *why* we have no idea [@rr].  See [@sipser:pnp] or [@gj] for more information.

Of course, even if there is no deterministic algorithm to solve $\mathsf{NP}$-complete problems in polynomial time, there might be a probabilistic algorithm, or a nonuniform algorithm (one that is different for each input length $n$).  But Karp and Lipton [@kl] showed that either of these would have a consequence, namely the collapse of the polynomial hierarchy, that seems almost as implausible as $\mathsf{P}=\mathsf{NP}$.  Also, Impagliazzo and Wigderson [@iw] gave strong evidence that $\mathsf{P}=\mathsf{BPP}$; that is, that 