Classical Complexity Classes (P, NP, PSPACE)

Table of Contents

1. Introduction
2. What Are Complexity Classes?
3. Deterministic vs Non-Deterministic Models
4. Class P (Polynomial Time)
5. Class NP (Nondeterministic Polynomial Time)
6. Relationship Between P and NP
7. NP-Complete Problems
8. Reductions and Hardness
9. Class PSPACE (Polynomial Space)
10. Relationships Among P, NP, and PSPACE
11. The Time and Space Hierarchy
12. Examples of Problems in Each Class
13. Practical Implications
14. Open Questions in Classical Complexity
15. Conclusion

---

1. Introduction

Complexity theory seeks to understand how much computational effort is needed to solve different problems. Classical complexity classes like P, NP, and PSPACE provide a framework for this analysis by categorizing problems according to the time and space resources required.

---

2. What Are Complexity Classes?

Complexity classes are sets of decision problems that can be solved by a machine (Turing machine) under specified constraints:

• Time: Number of steps to compute
• Space: Memory used during computation

---

3. Deterministic vs Non-Deterministic Models

• Deterministic Turing Machine (DTM): Executes a single computational path
• Non-Deterministic Turing Machine (NTM): Can explore multiple paths in parallel
• Many complexity classes are defined with respect to these models

---

4. Class P (Polynomial Time)

P is the set of decision problems that can be solved in polynomial time on a deterministic Turing machine.

\[
P = \{ L \mid \text{There exists a DTM that decides } L \text{ in } O(n^k) \text{ for some } k \}
\]

Examples:

• Sorting
• Finding the greatest common divisor
• Matrix multiplication
• Graph reachability

---

5. Class NP (Nondeterministic Polynomial Time)

NP is the set of problems for which a solution can be verified in polynomial time by a deterministic machine.

Equivalently:

• Solvable in polynomial time on a non-deterministic machine
• Or: Verifiable in polynomial time if a solution is guessed

Examples:

• Boolean satisfiability (SAT)
• Hamiltonian cycle
• Subset sum

---

6. Relationship Between P and NP

\[
P \subseteq NP
\]

• Every problem in P is trivially in NP
• The open question: Is \( P = NP \)?
• If true, many problems believed to be hard would be easy to solve

---

7. NP-Complete Problems

NP-complete problems are the hardest in NP:

1. They are in NP
2. Every NP problem can be polynomial-time reduced to them

Examples:

• SAT
• 3SAT
• Traveling Salesman Problem (decision version)
• Clique

If any NP-complete problem is in P, then P = NP

---

8. Reductions and Hardness

• Reduction: One problem transforms into another
• If \( A \leq_p B \) and \( B \in P \), then \( A \in P \)
• Used to prove problem difficulty and completeness

---

9. Class PSPACE (Polynomial Space)

PSPACE is the class of problems solvable in polynomial space on a deterministic machine, regardless of time.

\[
PSPACE = \{ L \mid \text{There exists a DTM that decides } L \text{ using } O(n^k) \text{ space} \}
\]

Includes all problems solvable with polynomial memory:

• May require exponential time
• Subsumes both P and NP

---

10. Relationships Among P, NP, and PSPACE

The following inclusions hold:

\[
P \subseteq NP \subseteq PSPACE
\]

Whether any of these inclusions are strict is still unknown, but most complexity theorists believe:

\[
P \ne NP \ne PSPACE
\]

---

11. The Time and Space Hierarchy

The hierarchy theorems show:

• More time → strictly more power
• More space → strictly more power

\[
\text{TIME}(n) \subsetneq \text{TIME}(n^2), \quad \text{SPACE}(n) \subsetneq \text{SPACE}(n^2)
\]

---

12. Examples of Problems in Each Class

Problem	Class
Sorting integers	P
SAT	NP-complete
Generalized chess	PSPACE-complete
Regular expression matching	P
TQBF (True Quantified Boolean Formula)	PSPACE-complete

---

13. Practical Implications

• P problems: Efficient and scalable
• NP problems: Often solved heuristically or with approximation
• PSPACE problems: Rarely tractable, used in logic, verification, and AI

---

14. Open Questions in Classical Complexity

• Is \( P = NP \)?
• Is \( NP = PSPACE \)?
• Are there problems in \( NP \setminus P \)?
• Do faster algorithms exist for known hard problems?

---

15. Conclusion

Classical complexity classes like P, NP, and PSPACE help us categorize problems based on their inherent difficulty and feasibility. Understanding these classes is crucial for algorithm design, cryptography, optimization, and the theoretical foundations of computer science.

---