NPluokat

NPluokat, or NP-luokat, is a Finnish term commonly used to refer to the computational complexity class NP. The NP class consists of decision problems for which a given "yes" instance can be verified in polynomial time if a suitable certificate is provided, or equivalently problems that can be solved in polynomial time by a nondeterministic Turing machine.

A key relationship is that P, the class of problems solvable in deterministic polynomial time, is contained within NP. Whether P equals NP remains one of the major open questions in computer science. NP-hard problems are at least as hard as the hardest problems in NP, in that every problem in NP can be reduced to an NP-hard problem in polynomial time. A problem is NP-complete if it is both in NP and NP-hard, making it among the most challenging problems in NP.

Common NP-complete problems include SAT (logical satisfiability), 3-SAT, CLIQUE, Vertex Cover, Hamiltonian Path, and Subset Sum in its decision form. Demonstrating that a problem is NP-hard typically involves a polynomial-time reduction from a known NP-hard problem, while showing membership in NP requires a polynomial-time verifier for proposed solutions.

These concepts have practical implications: many NP-complete problems resist efficient exact solutions for large instances, leading to reliance on heuristics, approximation algorithms, or restrictions to special cases. The study of NP and NP-completeness, initiated by Cook's theorem (1971) and strengthened by Karp's 21 NP-complete problems (1972), remains central to theoretical computer science.