Skip to interview prep
Apexed

390. Define P and NP. Why is every problem in P also in NP?

MediumComplexity classes

Technical
Show model answer

P is the class of decision problems solvable by a deterministic algorithm in time polynomial in the input size. NP is the class of decision problems where every 'yes' instance has a certificate of polynomial size that can be checked in polynomial time; equivalently, a nondeterministic machine can decide them in polynomial time. NP does not mean 'not polynomial'.

P ⊆ NP because a polynomial-time solver can serve as its own verifier: ignore the certificate and just solve the instance. Whether P = NP is open. Examples in NP: SAT (certificate is a satisfying assignment), Hamiltonian cycle (the cycle) and subset sum (the subset).

Define P and NP. Why is every problem in P also in NP — Data structures & algorithms interview question — Apexed