Wednesday, November 12, 2025

PNPPSPACEEXPTIMEEXPSPACE

P (Polynomial Time)
Decision problems solvable by a deterministic Turing machine in polynomial time.

NP (Nondeterministic Polynomial Time)
Decision problems where a "yes" answer can be verified in polynomial time.

PSPACE (Polynomial Space)
Problems solvable using polynomial space (but possibly exponential time).

EXPTIME (Exponential Time)
Problems solvable in exponential time O(2p(n)).

EXPSPACE (Exponential Space)
Problems solvable using exponential space O(2q(n)).

Note: P ⊂ EXPTIME and PSPACE ⊂ EXPSPACE are known strict inclusions,
but whether P = NP remains one of the most famous open problems in computer science.

No comments:

Post a Comment

Topological Invariants: What Doesn't Change Topological Invariants: What Doesn't Change ...