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.