---
title: "P, NP and What NP-Complete Means"
description: "P holds the problems solvable in polynomial time and NP the ones whose proposed answers can be checked that fast. NP-complete problems are the hardest in NP: every other NP problem reduces to them, so"
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-09-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 holds the problems solvable in polynomial time and NP the ones whose proposed answers can be checked that fast. NP-complete problems are the hardest in NP: every other NP problem reduces to them, so a fast method for one would be a fast method for all.

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: Easy to Check, Hard to Solve

Some problems split into two questions: how hard is it to find an answer, and how hard is it to check one. P holds the problems you can solve in polynomial time, meaning the work grows manageably as the input grows. NP holds the problems where a proposed answer can be checked in polynomial time, even if finding it is slow. Checking can be easy while solving stays hard.

**Example.** Take coloring a map with three colors so that neighbors always differ. The coloring itself is the certificate for a yes answer. To check it, you walk every shared border and confirm the two sides differ. That walk stays quick even for a big map, which is exactly what membership in NP asks for.

A reduction translates one problem into another in polynomial time, so a fast solver for the second problem would solve the first one too. An NP-complete problem sits inside NP, and every other NP problem reduces to it. That is why one polynomial algorithm for a single NP-complete problem would make all of NP solvable in polynomial time.

**Tip.** NP-hard and NP-complete are not the same claim. NP-hard means at least as hard as the hardest problems in NP. NP-complete adds membership: the problem is in NP too. If no quick check exists for its answers, call it NP-hard and stop there.

**Recap.** P means quick to solve, NP means quick to check, and NP-complete means in NP with every NP problem reducing to it.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [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)
- [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)
- [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)