Decision classes P and NP
Polynomial solving and polynomial verification differ.
Key knowledge
P contains decision problems solved by a deterministic algorithm in time polynomial in input length. NP contains problems whose yes instances admit polynomial-size certificates verified in polynomial time, with no accepted certificate for no instances. P⊆NP.
Conditions and scope
- Fix a conventional discrete machine model and explicit finite input encoding.
- NP does not mean non-polynomial; polynomial bounds are asymptotic rather than a practical speed guarantee.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Physical pages 2–3: polynomial decision/verification, certificate conditions, reductions and NP-completeness.
2026-10-10 · P, NP and verifier quantifiers; no claimed resolution of P versus NP.
Entry details
Permanent link to this entry ↗- Record identity
- info-complexity-p-np
- Revision
- university-reference.1
- Structured reference record
- University reference