Completeness for other complexity classes
Problems complete for classes other than NP: P (circuit value), NL (s-t connectivity), coNP (UNSAT), PSPACE (TQBF, Geography), levels of the polynomial hierarchy (QSAT_k), EXP, NEXP and EXPSPACE (succinct problems, regular expressions with squaring).
- Circuit value problem
- Directed s-t connectivity
- Generalized geography
- Quantified Boolean formulas with bounded alternation
- Regular expressions with squaring
- Satisfiability and model checking for the linear-time μ-calculus
- Satisfiability of the modal μ-calculus
- Succinct 3SAT
- Succinct circuit value problem
- True quantified Boolean formulas
- Unsatisfiability
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.