any probabilistic algorithm can be simulated by a deterministic one with polynomial slowdown.

It is known that $\mathsf{P}\neq\mathsf{NP}$ in a black box or oracle setting [@bgs].  This just means that any efficient algorithm for an $\mathsf{NP}$-complete problem would have to exploit the problem’s structure in a nontrivial way, as opposed to just trying one candidate solution after another until it finds one that works.  Interestingly, most of the physical proposals for solving $\mathsf{NP}$-complete problems that we will see do *not* exploit structure, in the sense that they would still work relative to any oracle.  Given this observation, I propose the following challenge: *find a physical assumption under which* $\mathsf{NP}$*-complete problems can provably be solved in polynomial time, but only in a non-black-box setting.*

Soap Bubbles et al.\[SOAP\]
===========================

Given a set of points in the Euclidean plane, a *Steiner tree* (see Figure \[steiner\]) is a collection of line segments of minimum total length connecting the points, where the segments can meet at vertices (called Steiner vertices) other than the points themselves.  Garey, Graham, and Johnson [@ggj] showed that finding such a tree is $\mathsf{NP}$-hard.[^2]  Yet a well-known piece of computer science folklore maintains that, if two glass plates with pegs 