Complexity Classes?

Randomly choose an element and evaluate in polynomial time (Non-deterministic P)

1. Deterministic vs. Nondeterministic Computation

A deterministic machine behaves like a normal computer:
given an input and a current state, it has exactly one possible next action.
It follows a single, predictable computation path.

A nondeterministic machine is a theoretical model that can
magically guess a correct solution among many possibilities.
If a valid witness exists, the machine chooses it instantly and then
verifies it using a deterministic algorithm that must run in polynomial time.

This “guess + verify” idea is the foundation of the complexity class $~NP~$.

2. Polynomial-Time Computation: P and NP

Polynomial time refers to any running time of the form

\[n^k \quad \text{for some constant } k.\]

• P is the class of problems solvable in polynomial time on a deterministic machine.
  These are considered “efficiently solvable.”

• NP is the class of problems whose solutions (called witnesses)
  can be verified in polynomial time on a deterministic machine.
  Equivalently, NP is the class solvable in polynomial time on a nondeterministic machine.

Because deterministic computation is weaker than nondeterministic guessing, we know:

\[P \subseteq NP.\]

Whether $~P = NP~$ or $~P \neq NP~$ is one of the most famous open problems in computer science.

3. Reductions and How Problems Become Equivalent

To compare the difficulty of two problems, we use polynomial-time reductions.

A problem $~A~$ reduces to a problem $~B~$ (written $~A \le_p B~$)
if any instance of $~A~$ can be transformed into an instance of $~B~$
in polynomial time such that solving $~B~$ solves $~A~$.

This gives us a formal notion of difficulty:

• If $~A \le_p B~$, then $~B~$ is at least as hard as $~A~$.
• If two problems reduce to each other, they are equivalent in complexity.

This reduction idea is what allows us to define NP-complete problems.

4. NP-Complete Problems: The Hardest Problems in NP

A problem $~C~$ is NP-complete if:

1. $~C \in NP~$, and
2. every NP problem reduces to $~C~$:

\[\forall A \in NP,\; A \le_p C.\]

This means NP-complete problems are the hardest problems inside NP.
If any NP-complete problem is solved in polynomial time, then:

\[P = NP.\]

Examples include SAT, 3-SAT, Clique, Vertex Cover,
and Traveling Salesman (decision version).

Even though these problems look very different,
polynomial-time reductions show that they all have exactly the same computational difficulty.

5. PSPACE and PSPACE-Complete Problems

Above NP lies the larger class PSPACE,
the class of problems solvable with polynomial space (memory),
regardless of how much time is required.

A PSPACE algorithm may run for exponential time,
as long as it reuses its space efficiently.

A problem is PSPACE-complete if:

1. it can be solved in polynomial space, and
2. every PSPACE problem reduces to it.

The classic PSPACE-complete problem is QBF
(Quantified Boolean Formula), which extends SAT by allowing
alternating existential and universal quantifiers like $~\exists~$ and $~\forall~$.
This creates a game-like logical structure that requires significantly more power to analyze.

PSPACE-complete problems are believed to be much harder than NP-complete problems.

The Polynomial Hierarchy: $\Sigma_k$ and $\Pi_k$

Between NP and PSPACE lies a layered structure called the Polynomial Hierarchy (PH).
It refines NP by counting how many layers of nondeterminism and universality
(“there exists” vs. “for all”) a problem requires.

Layers of the hierarchy

• $~\Sigma_1 = NP~$
  (Exists-witness form: “$\exists x$ such that the condition is satisfied”)

• $~\Pi_1 = coNP~$
  (For-all-witness form: “$\forall x$ the condition holds”)

Higher levels alternate quantifiers:

• $~\Sigma_2~$: problems expressible like
  \(\exists x_1 \; \forall x_2 \; \phi(x_1, x_2)\)
• $~\Pi_2~$:
  \(\forall x_1 \; \exists x_2 \; \phi(x_1, x_2)\)

And so on:

\[\Sigma_1 \subseteq \Sigma_2 \subseteq \Sigma_3 \subseteq \dots\] \[\Pi_1 \subseteq \Pi_2 \subseteq \Pi_3 \subseteq \dots\]

6. Higher Levels Above PSPACE

Beyond PSPACE, there are even stronger complexity classes:

• EXPTIME: problems solvable in exponential time
• EXPSPACE: exponential space
• Undecidable problems: problems no algorithm can solve in general

Each class is believed to strictly contain the one below it (though some separations are unproven).

7. The Big Picture

Here is the widely believed hierarchy of complexity classes:

\[P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq EXPSPACE \subsetneq \text{Undecidable}.\]

Inside NP:

\[P \subseteq NP \supseteq \text{NP-complete}.\]

• P: efficiently solvable
• NP: efficiently verifiable
• NP-complete: hardest problems inside NP
• PSPACE: problems solvable with polynomial space
• PSPACE-complete: hardest problems in PSPACE
• Higher classes: even more powerful or even unsolvable problems

This provides the overall structure of classical complexity theory.