CampusDownWiki
Total citations 126,015한국어KO 12,862EnglishEN 77,490日本語JA 9,775中文ZH 25,888
CampusDown ↗
English

P versus NP problem

➗ Mathematics & Statistics By CampusDown Wiki Editorial Team Last updated Views 1
P versus NP is one of computer science's biggest open questions: if a proposed solution to a problem can be checked quickly, can the problem also be solved quickly? It's one of the Clay Mathematics Institute's seven Millennium Prize Problems.
Contents
  1. 1. The dorm-room example
  2. 2. What P and NP mean
  3. 3. A $1 million question
  4. 4. FAQ
  5. 5. References

Finishing a 1,000-piece jigsaw takes hours. Checking that someone else finished it takes seconds. Is that gap real, or have we just not found a clever enough method? That's P versus NP.

Illustration of one student frowning over a scattered jigsaw puzzle while another student calmly checks a finished puzzle with a magnifying glass
Solving is hard. Checking is quick. Are they really different?

The dorm-room example

The Clay Mathematics Institute describes it like this. You have 400 students and room for only 100 in a dorm. The dean hands you a list of pairs who can't live together. Checking a proposed list of 100 is easy: just make sure no banned pair is on it. Finding such a list from scratch is another story: the number of ways to pick 100 of the 400 students is greater than the number of atoms in the known universe, so no computer could just try them all.

What P and NP mean

Comparison of P and NP: P problems can be solved quickly, like sorting a list; NP problems can at least be checked quickly once someone hands you an answer, like verifying a completed sudoku or a list of compatible roommates
Fast to solve vs. fast to check.

P is the set of problems a computer can solve quickly. NP is the set of problems where a proposed answer can be checked quickly. Clay's own shorthand: P is "easy to find," NP is "easy to check."

The big question: is every easy-to-check problem secretly easy to solve? If yes, P = NP. Most researchers suspect not, but nobody has proved it either way.

A $1 million question

Stephen Cook and Leonid Levin formulated the problem independently in 1971. In 2000 the Clay Institute picked it as one of seven Millennium Prize Problems, with $1 million for each solution. So far only one of the seven, the Poincaré conjecture, has been resolved.

FAQ

What does NP stand for?
Nondeterministic polynomial time. In plain terms: answers can be checked quickly.
Has anyone solved P vs NP?
No. It's still open, and the Clay prize is unclaimed.
Why does it matter?
It decides whether lots of hard scheduling, routing, and security problems have fast solutions.

Sources reviewed: 2026-11-20

References

  1. Clay Mathematics Institute. P vs NP. Official problem page: easy to check vs. easy to solve, the dormitory example, Cook and Levin 1971.
  2. Clay Mathematics Institute. The Millennium Prize Problems. Seven problems named in 2000, $1 million each; only the Poincaré conjecture solved.

Found this helpful? Share it

Send it to a friend who needs it.

X Facebook Threads

Reports and materials that use this theory (Korean)

There are no materials dedicated to this theory yet, but you can search related reports in the CampusDown library (Korean).

Find more reports · Search 'P 대 NP 문제' on CampusDown →

You may also like

This article was last updated on November 20, 2026. It is based on widely recognized original works and textbooks; when citing it in a paper, please check the original sources listed in the references.