NP

NP
Name	NP
Domain	Theoretical computer science
Introduced	1971
Notable contributors	Stephen Cook, Leonid Levin, Richard Karp, Michael Rabin, Dana Scott
Related concepts	P (complexity), NP-complete, Co-NP, PSPACE, EXPTIME
Canonical problem	Boolean satisfiability problem

NP

NP is the class of decision problems for which a proposed solution can be verified efficiently by a deterministic algorithm given a finite certificate. Originating in the work of Stephen Cook and Leonid Levin, NP occupies a central role in the study of computational hardness alongside classes such as P (complexity), PSPACE, and EXPTIME. NP frames questions across fields including Boolean satisfiability problem, graph isomorphism problem, Hamiltonian cycle problem, and integer factorization by focusing on nondeterministic verification within polynomial time.

Definition and Formalization

Formally, NP consists of languages L for which there exists a deterministic polynomial-time verifier V and a polynomial p such that for all inputs x: x ∈ L iff there exists a certificate y with |y| ≤ p(|x|) and V(x,y) accepts. This definition relates to nondeterministic Turing machines introduced in models by Alan Turing and later formalized by Michael Rabin; an equivalent characterization states that NP is the set of languages decidable by nondeterministic Turing machines in polynomial time. Alternative formalizations employ proof systems like Cook–Levin reductions used by Stephen Cook and reductions central to work by Richard Karp.

Examples and Complete Problems

Classic NP-members include Boolean satisfiability problem (SAT), Clique problem, Vertex cover problem, Hamiltonian path problem, Subset sum problem, 3-SAT, Graph coloring problem, and Independent set problem. NP-complete problems are those in NP to which every other NP problem can be reduced in polynomial time; seminal NP-complete problems were identified in Cook–Levin theorem and the list expanded by Richard Karp in his 1972 paper listing twenty-one NP-complete problems. Other known NP-complete instances include Traveling salesman problem (decision variant), Partition problem, Set cover, Feedback vertex set, and Maximum cut (decision form). Problems suspected to be in NP but not NP-complete include Graph isomorphism problem and certain instances of integer factorization under specific encodings.

Computational Complexity and Relationships

NP is related to numerous complexity classes: P (complexity) is contained in NP, while the major unresolved question is whether P (complexity) = NP. The complement class Co-NP contains languages whose complements are in NP, with prominent questions about equality between NP and Co-NP. Containments include NP ⊆ PSPACE ⊆ EXPTIME, with separations such as Time hierarchy theorem and Space hierarchy theorem providing partial structure. Reductions used to compare problem hardness include polynomial-time many-one reductions and Turing reductions, tools developed in the literature by Stephen Cook, Richard Karp, and Leonid Levin. Structural results involve probabilistic classes like BPP and counting classes like #P introduced by Leslie Valiant, with Toda's theorem linking PH to #P.

Algorithms and Approaches

Despite NP’s worst-case intractability for many NP-complete problems, a range of algorithmic strategies exist: exact exponential-time algorithms and branching techniques used in studies by Richard Karp and later algorithm designers; approximation algorithms with performance guarantees developed in connection with Vazirani and David Johnson; parameterized algorithms and fixed-parameter tractability (FPT) frameworks advanced by Downey and Fellows; randomized algorithms and heuristics such as Monte Carlo methods and simulated annealing applied to instances like Boolean satisfiability problem and Traveling salesman problem; and SAT solvers implementing DPLL and conflict-driven clause learning (CDCL) inspired by work from Davis–Putnam–Logemann–Loveland and modern SAT community. Semidefinite programming relaxations and primal-dual methods underpin approximation schemes for problems like Max Cut using techniques from Goemans–Williamson.

Practical Implications and Applications

NP and NP-complete problems are pervasive in applied domains: combinatorial optimization tasks in network design exemplified by Steiner tree problem and Minimum spanning tree variants; cryptographic constructions relying on presumed hardness of problems such as integer factorization and discrete logarithm instantiations used in RSA (cryptosystem) and Diffie–Hellman key exchange; operations research formulations like scheduling and vehicle routing related to Travelling Salesman Problem and Job shop scheduling; bioinformatics problems including motif finding and haplotype assembly; and verification tasks in software and hardware design that reduce to instances of Boolean satisfiability problem and model checking associated with SAT solvers and SMT (satisfiability modulo theories). Industry-grade heuristics, approximation, and specialized solvers enable practical handling of many NP instances despite worst-case hardness established through reductions and NP-completeness proofs.

Open Problems and Research Directions

Major open problems include the central P versus NP question posed by Stephen Cook and Leonid Levin, the relationship between NP and Co-NP, the status of problems like Graph isomorphism problem and integer factorization under classical and quantum models (e.g., relevance to Shor's algorithm), and structural questions about the polynomial hierarchy PH. Research directions explore average-case complexity such as work by Levin (average-case), fine-grained complexity connecting concrete time bounds across problems by researchers like Ryan Williams and Virginia Vassilevska Williams, kernelization in parameterized complexity advanced by Downey and Fellows, and quantum complexity classes such as BQP and their intersections with NP. Progress on these topics would have profound consequences for cryptography, optimization, and theoretical foundations across computing.

Category:Complexity classes