Tag Info

Questions related to the (computational) complexity of solving problems

Complexity theory classifies problems with respect to their computational hardness, i.e. which machine models can solve them under which restrictions, and the relations between these classes like the famous $\sf{P}$ and $\sf{NP}$ classes.

Computational complexity is about the inherent difficulty of computational problems, when some resource is limited and the impossibility of solving a problem within particular resource bounds (lower-bounds).

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.

The tag is more suitable 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 tags and . For questions asking for an algorithm to solve a particular problem, or upper-bounds on resources required to solve a problem, consider using .