P versus NP problem

The open question of whether every decision problem whose proposed solution can be verified in polynomial time can also be solved in polynomial time.

P (complexity): The class of decision problems solvable by a deterministic algorithm in polynomial time. P is the class on the solving side of the question.
NP-completeness: The study of problems in NP to which every problem in NP can be reduced in polynomial time. An NP-complete problem in P would establish P = NP.
co-NP: The class of decision problems whose complements belong to NP. Whether NP equals co-NP is related but distinct from whether P equals NP.
Integer factorization: The problem of expressing a composite integer as a product of prime factors. Factoring is in NP and co-NP, but its status as NP-complete is unknown.
NP (complexity): The class of decision problems whose yes-instances have certificates verifiable in polynomial time. NP is the class whose problems are tested against efficient solving.
Polynomial-time reduction: A transformation computable in polynomial time that preserves yes-or-no answers between problems. Reductions compare problem difficulty and transfer efficient algorithms.
BPP (complexity): The class of decision problems solvable with bounded error by probabilistic polynomial-time algorithms. Randomized polynomial time offers a different model of efficient solving.
Cryptography: The practice and study of securing information through mathematical methods. Many cryptographic assumptions concern problems believed computationally hard, though P ≠ NP alone would not guarantee security.
Polynomial time: A running-time bound proportional to a polynomial in the input length. Polynomial time defines efficiency for both solving and verification.
Certificate (complexity theory): A concise proposed witness that can be checked efficiently to establish a yes-instance. Certificates express the verification advantage central to NP.

Linked from 27 pages