Tag Info

P versus NP and other resource-bounded computation.

Computational complexity is about the inherent difficulty of computational problems, when some resource is limited.

Time and space are the most common resource limits. These restrict the number of steps or tape squares that a Turing machine may use. Less common limits are the number of alternations, nondeterministic steps, bits of advice, or quantum bits used in the computation.

In the $\rm{P} \overset{?}{=} \rm{NP}$ question, time is polynomially bounded in the size of the input. This question asks whether polynomially many nondeterministic steps can decide some problem for which polynomially many deterministic steps is not enough.

Computability is a better tag when only very weak limits are placed on the allowed computations, for instance when the computation may use any finite amount of time.

For interactions that can continue indefinitely, consider instead the tag distributed-systems.