A complexity class is a collection of computational problems sharing specified resource bounds and a computational model.
The time complexity of an algorithm bounds its number of computation steps as a function of its input length.
An algorithm runs in polynomial time when its running time is at most for some constant , where is the input length.
is the class of decision problems whose positive instances have polynomial-length certificates verifiable in polynomial time. Equivalently, it is polynomial time on a nondeterministic computation.
A certificate for a positive instance is a polynomial-length string that makes a polynomial-time verifier accept that instance.
The space complexity of an algorithm bounds the amount of working memory it uses as a function of input length.
A decision problem is NL-complete when it belongs to NL and every problem in NL reduces to it by a deterministic logarithmic-space many-one reduction.
The directed graph reachability problem asks whether a directed graph contains a directed path from a specified vertex to a specified vertex . It is NL-complete.
The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.
consists of complements of languages in NL.
The Immerman–Szelepcsényi theorem states that . Its proof uses inductive counting of reachable configurations.
Articles by others on the same topic
Complexity classes are categories used in computational theory to classify problems based on the resources needed to solve them, such as time and space. They help in understanding how difficult a problem is to solve, depending on the computational model used. ### Key Complexity Classes: 1. **P (Polynomial Time)**: - Contains decision problems that can be solved by a deterministic Turing machine in polynomial time. Problems in P are generally considered "efficiently solvable.
