--- title: "P, NP and What NP-Complete Means" description: "P contains decision problems solvable in polynomial time. NP contains decision problems whose yes answers have polynomial-length certificates checkable in polynomial time. NP-complete means both in NP" canonical: https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB source: https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # P, NP and What NP-Complete Means P contains decision problems solvable in polynomial time. NP contains decision problems whose yes answers have polynomial-length certificates checkable in polynomial time. NP-complete means both in NP and NP-hard. A polynomial algorithm for one NP-complete problem would imply P = NP. Subject: Computing · Area: Algorithms & Data Structures · Ages 21 to 22 Page: https://lightmysky.com/learn/computing/p-np-and-what-np-complete-means-mt_wwmNVG_VnB ## Ready when they can - Give a certificate for a yes-instance of a named NP problem and check it in polynomial time - Explain what would follow if any single NP-complete problem had a polynomial algorithm - Say why NP-hard and NP-complete are not the same claim ## Lesson: Polynomial solving and certificate checking P contains yes-or-no decision problems with a deterministic algorithm whose worst-case runtime is bounded by a fixed polynomial in input length n. A bound c times n^k uses constants c and k independent of the input. Polynomial time need not be practical: large constants or powers can still be costly. Fast runs on selected inputs do not establish a polynomial worst-case bound. NP contains decision problems whose yes answers have polynomial-length certificates checked in polynomial time. A yes input has at least one accepted certificate; a no input has none. Every problem in P is also in NP. Whether P equals NP is open. Failure to find a polynomial verifier does not prove that none exists. **Example.** For three-color map coloring, ask whether each region can receive red, green or blue with different colors across every shared border. A certificate lists one allowed color per region. Check the color list and every border. With V regions and E borders in an adjacency-list representation, checking takes O(V + E) time. A rejected coloring does not rule out another valid coloring. *(drawing: Rejecting one coloring does not prove that the map has no valid three-coloring.)* A problem is NP-hard if every problem in NP has an answer-preserving polynomial-time reduction to it. It is NP-complete if it is also in NP. NP-hardness alone neither establishes NP membership nor excludes it. To claim NP-completeness, prove both the reductions and polynomial certificate verification. You have seen how reductions reuse a target solver. Every NP problem reduces to any NP-complete problem. A polynomial-time algorithm for one NP-complete problem would therefore put all of NP in P. Since P is already contained in NP, this would prove P = NP. It would not automatically make every implementation practical. **Recap.** P has polynomial-time decision algorithms. NP has polynomially checkable short yes certificates. NP-complete means in NP and NP-hard. Whether P = NP is open. *Original lesson, questions and flashcards written for this learning dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Reductions: Solving One Problem by Turning It into Another](https://lightmysky.com/learn/computing/reductions-solving-one-problem-by-turning-it-into-another-mt_PAwby3ZyAr) ## Optional connections - [The Halting Problem: A Task No Program Can Do](https://lightmysky.com/learn/computing/the-halting-problem-a-task-no-program-can-do-mt_KeuKGHFWqr) - [Turing Machines and the Universal Machine](https://lightmysky.com/learn/computing/turing-machines-and-the-universal-machine-mt_vS_QC1tCSM) ## Opens up - [Complexity Beyond NP: Space, Randomness and the Hierarchy](https://lightmysky.com/learn/computing/complexity-beyond-np-space-randomness-and-the-hierarchy-mt_ADfgl9UGpO) - [SAT Solvers and What Makes Search Practical](https://lightmysky.com/learn/computing/sat-solvers-and-what-makes-search-practical-mt_d46m2LD443) - [Euler Trails and Hamilton Cycles](https://lightmysky.com/learn/mathematics/euler-trails-and-hamilton-cycles-mt_RU5P5Iqekt) - [Living with NP-Hardness: Approximation and Heuristics](https://lightmysky.com/learn/computing/living-with-np-hardness-approximation-and-heuristics-mt_tZ82ty6h2u)