A “guess box” is an instrument that explores many computational worlds
at once. If we place a computer program *P* and a number *k* into a
guess box, the program *P* runs on every binary string of length *k*
simultaneously. Each run of *P* is isolated; it cannot communicate
with any other running *P* and inhabits a world defined by a
**single** k-bit string. If any run of *P* prints “yes,” the guess box
will print “yes.” Otherwise, the guess box prints “no.”

The runtime of the guess box is just the runtime of *P*. This seems
like an unreasonable model of computation, because it is: the guess
box allows massively parallel search for free. One could reasonably
expect that it would be easy to prove that “guess boxes” can’t be
efficiently constructed.

In fact, one version of this question (“can we build an efficient
guess box”) asks if **P** is different from **NP**, a major open
problem in complexity theory. This website will collect resources
about nondeterministic time, including descriptions of current open
problems that refine **P** vs **NP** in a variety of interesting ways.