ADVANCED ALGORITHMS - NP-COMPLETENESS:Complexity Classes: PSPACE, co-NP and the Hierarchy

Complexity Classes: co-NP, PSPACE and the Hierarchy

A Map of Complexity Classes

EXPTIME
  └── PSPACE
        ├── NP ──── co-NP
        │    └── P
        │         └── NC (highly parallelizable)
        └── (NP ∩ co-NP) includes factoring, primality, ...

It is known that P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and P ≠ EXPTIME. Whether P = NP is the most famous open problem in computer science.

co-NP

A problem L is in co-NP if its complement (is the answer NO?) is in NP — equivalently, if NO instances have short, efficiently-verifiable certificates.

co-NP-complete examples:

• Unsatisfiability (UNSAT): Is this Boolean formula always false?
• Tautology: Is this formula always true?
• Primes (historically — now proven to be in P by AKS algorithm, 2002)

Key insight: If P ≠ NP, then NP ≠ co-NP. Many believe NP ∩ co-NP contains problems strictly between P and NP-complete (like integer factoring).

PSPACE

PSPACE = problems solvable by a Turing machine using polynomial space (memory), with no time restriction.

Since a poly-space machine can revisit configurations, it can run for exponential time.

PSPACE-complete (hardest problems in PSPACE):

• QBF (Quantified Boolean Formula): Is ∃x₁ ∀x₂ ∃x₃ … φ(x₁, …, xₙ) true?
• PSPACE-complete games: Geography, Generalized Chess, Go on an n×n board
• Planning problems: AI planning with polynomial plan length

def qbf_eval(formula, quantifiers, var_idx, assignment):
    """
    Evaluate QBF recursively. Exponential time, polynomial space.
    quantifiers: list of ('exists' or 'forall', variable_index)
    """
    if var_idx == len(quantifiers):
        return evaluate_formula(formula, assignment)
    
    quant, var = quantifiers[var_idx]
    
    if quant == 'exists':
        # True if there EXISTS a value making the rest true
        return (qbf_eval(formula, quantifiers, var_idx + 1, {**assignment, var: True}) or
                qbf_eval(formula, quantifiers, var_idx + 1, {**assignment, var: False}))
    else:  # forall
        # True if ALL values make the rest true
        return (qbf_eval(formula, quantifiers, var_idx + 1, {**assignment, var: True}) and
                qbf_eval(formula, quantifiers, var_idx + 1, {**assignment, var: False}))

The Polynomial Hierarchy (PH)

Between NP and PSPACE lies the polynomial hierarchy, defined by alternating quantifiers:

• Σ₁ᵖ = NP: ∃ witness, poly-time verifier
• Π₁ᵖ = co-NP: ∀ assignments, poly-time check
• Σ₂ᵖ: ∃ x ∀ y P(x, y) — one alternation of quantifiers
• Πₖᵖ: k alternations of quantifiers

Example: "Is the minimum of a function ≤ k?" is Σ₂ᵖ if the function has a co-NP encoding.

If P = NP, the entire hierarchy collapses to P.

EXPTIME

Problems solvable in exponential time (2^{poly(n)}):

• Generalized Chess: Determining the winner of a chess position on an n×n board
• Succinct graph problems: Graph encoded as a circuit rather than adjacency matrix
• WS1S (weak monadic second-order theory of one successor): Decision procedure for certain logic formulas

Practical Takeaways

Practice Problems

1. Is the problem "Given DNF formula, is it a tautology?" in P, NP, co-NP, or all three?
2. Show that QBF is PSPACE-complete (sketch the reduction from any PSPACE problem)
3. Where does Graph Isomorphism sit? (It's in NP ∩ co-NP but not known to be in P or NP-complete)
4. Why does integer factoring being in NP ∩ co-NP not imply it is in P?