Computational Complexity Theory

← Back to Domain-Specific Abstractions by Domain

2 domain-specific abstractions whose origin domain is Computational Complexity Theory.

• Parity P — The complexity class of decision problems for which a nondeterministic polynomial-time machine accepts exactly when it has an odd number of accepting computation paths.
• Polynomial hierarchy — A nested hierarchy of decision-problem classes formed by bounded alternations of existential and universal polynomial-time computation, generalizing NP and coNP within PSPACE.