P vs NP: Computational Complexity Relationships

1. Origin of the P Complexity Class

The class P consists of decision problems solvable by a deterministic Turing machine in polynomial time. This class emerged from 1960s research on feasible computation (Cobham, Edmonds, Hartmanis, Stearns) to capture problems considered tractable in practice. P is a fundamental complexity class, not derived from NP or other classes.

2. NP and the Cook-Levin Theorem

NP contains decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine.

Cook-Levin Theorem (1971): Boolean satisfiability (SAT) is NP-complete. This means SAT is in NP and every problem in NP can be reduced to SAT in polynomial time. Therefore, if SAT ∈ P, then NP ⊆ P, which would imply P = NP.

3. The "P Increasing" Concept

If "P is increasing" means we are discovering more efficient algorithms that move problems from higher complexity classes into P (e.g., the AKS algorithm showing primality testing ∈ P in 2002), this demonstrates algorithmic progress. However, this gradual expansion of P does not necessarily imply all NP problems will eventually be in P, unless SAT itself is shown to be in P.

4. Intersection of P and NP

If SAT ∈ P, then NP ⊆ P by the Cook-Levin theorem. Since P ⊆ NP is always true (any efficiently solvable problem is efficiently verifiable), this would mean P = NP. In this scenario, the intersection P ∩ NP would equal NP, and NP-complete problems like SAT would reside in this intersection.

5. Current Understanding

At present, SAT is not known to be in P, and most complexity theorists believe P ≠ NP. Therefore, the current relationship is:

• P ⊆ NP (proper inclusion unknown)
• NP-complete problems are believed to be outside P
• P ∩ NP-complete = ∅ unless P = NP

Summary: P originates from the study of feasible computation. By the Cook-Levin theorem, if any NP-complete problem is in P, then P = NP. While P may expand through algorithmic discoveries, this does not necessarily lead to P = NP unless an NP-complete problem like SAT is shown to be in P.