In this article
Before you start
This page is part of the coding interview path. It needs no code, only three ideas.
Why interviewers ask this
Sooner or later a coding round hands you a problem that looks easy and refuses to give way: schedule these jobs perfectly, pick the best subset, visit every city once. The interviewer wants to see whether you can tell a problem that needs a cleverer algorithm from one that is believed to have no fast algorithm at all.
A weak answer says "NP means not polynomial" and stops, or declares the problem impossible. A strong answer defines the term correctly, says what it does and does not imply, and then offers a practical route: exact search for small inputs, an approximation, a heuristic, or a special case that is easy. A Staff-level answer also explains how the hardness is proved, using a reduction in the right direction, and knows that P versus NP is still open. Contrast this with the polynomial-time problems elsewhere on the path, such as topological sort or cycle detection in a directed graph.
NP-completeness from first principles
- NP-complete
- An NP-complete problem is a decision problem that is in NP and is also NP-hard. NP-complete problems are the hardest problems in NP, because a polynomial-time algorithm for any one of them would give one for every problem in NP.
- NP-hard
- An NP-hard problem is a problem that every problem in NP reduces to in polynomial time. It is at least as hard as everything in NP, and it does not have to be in NP itself.
- Polynomial-time reduction
- A polynomial-time reduction from problem A to problem B is a conversion, running in polynomial time, that turns any instance of A into an instance of B with the same yes or no answer. A fast solver for B then gives a fast solver for A.
- Certificate
- A certificate is a piece of evidence, such as a proposed solution, that lets a verifier confirm a yes answer in polynomial time. The verifier is the checking procedure.
In plain words
Picture a jigsaw puzzle. Checking a finished puzzle takes a glance. Finding the finished puzzle from a box of pieces can take hours.
Complexity theory sorts problems by that gap. NP is the class of decision problems whose yes answers can be checked in polynomial time. P is the class of decision problems that can be solved in polynomial time. The analogy breaks in one place: a real puzzle has a fixed size, while the theory asks what happens as the input grows without limit.
In one precise sentence, an NP-complete problem is a hardest problem in NP, defined by two properties: easy to check, and everything in NP reduces to it.
Step 1: A problem is in NP when its yes answers check quickly
A problem is in NP if a verifier can confirm any yes answer in polynomial time, given a certificate. Washington's Computer Science and Engineering (CSE) 421 lecture puts it as problems that have polynomial-time verifiers, and notes that the definition does not say whether a polynomial-time solver exists.
Take Boolean satisfiability (SAT): given a logical formula built from variables, "and", "or" and "not", is there a true-or-false assignment that makes it true? The certificate is one assignment. The verifier plugs it in and reads the formula once, which takes time proportional to the formula's length. Input: a formula and an assignment. Output: yes or no, quickly.
The name matters. The same Washington lecture says NP stands for nondeterministic polynomial. They do not mean "non-polynomial". You now know the first half of the definition: checking is cheap.
Step 2: A problem is NP-hard when all of NP reduces to it
A polynomial-time reduction converts instances of one problem into instances of another. Bristol's handout defines a decision problem L as NP-hard if, for every problem in NP, there is a polynomial-time reduction to L.
Read that as a ranking. If L has a fast algorithm, then every NP problem has one: convert the instance, then run L's algorithm. So L is at least as hard as anything in NP. Input: any NP instance. Output: an instance of L with the same answer.
An NP-hard problem is not required to be in NP. Erickson's notes define NP-hard through the same fast-algorithm implication, then call a problem NP-complete if it is both NP-hard and in NP. The halting problem is a well-known NP-hard problem that is not in NP (see Wikipedia on NP-hardness). Next: how a single problem is shown to be in this top group.
Step 3: Prove a new problem NP-complete by reducing a known one to it
To prove a problem X is NP-complete, you show two things. First, X is in NP: describe a polynomial-time verifier. Second, X is NP-hard: give a polynomial-time reduction from a problem already known to be NP-complete, such as SAT, to X. The direction is the whole point: reduce from the known hard problem to X.
Why that way? Suppose X had a fast algorithm. Then the known hard problem K would also have one, by converting each K instance into an X instance. But everything in NP reduces to K, so everything in NP would be fast. Hence X is as hard as K. Reducing X to K shows only that X is no harder than K.
This chain needs a first link. Cook (1971) published it, and Levin independently in 1973, as Erickson's notes record: satisfiability, in Erickson's form circuit satisfiability, is NP-complete. Karp (1972) then used many-one reductions from SAT to show 21 problems NP-complete; see the secondary summary. Karp's list includes clique, vertex cover, Hamiltonian cycle, graph coloring (chromatic number) and knapsack.
Step 4: One fast algorithm would settle P versus NP
If any NP-complete problem had a polynomial-time algorithm, every problem in NP would, per Erickson. That would mean P equals NP. Most researchers believe P does not equal NP, because decades of effort have produced no fast algorithm for any NP-complete problem, but that is a belief, not a proof.
The Clay Mathematics Institute lists P versus NP as a Millennium Prize problem and glosses P as easy to find and NP as easy to check. Nobody has proved either answer. So "NP-complete" means no polynomial-time algorithm for all inputs is known, and none is proved impossible. Input: a hard-looking problem. Output: a label that tells you which solutions to stop hoping for.
Step-by-step description
- A yes answer can be verified in polynomial time.
- Every NP problem reduces to it.
- A known hard problem reduces to the new one.
- A fast solver for one solves all of NP.
- A problem is in NP when its yes answers can be checked in polynomial time.
- A problem is NP-hard when every NP problem reduces to it.
- To prove a new problem NP-complete, reduce a known NP-complete problem to it.
- One fast algorithm for any NP-complete problem would settle P versus NP.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Three computed pictures make the definitions concrete.
Why brute force fails. A formula with n variables has 2ⁿ assignments, and each can be checked quickly. At an illustrative one billion checks per second, 20 variables take about a thousandth of a second, 40 variables about 18.3 minutes and 60 variables about 36.5 years.1
Why counting is hopeless. The Clay example picks a group from a larger pool of applicants and says the number of ways exceeds the atoms in the known universe. For 100 chosen from 400 the exact count is about 2.24 × 10⁹⁶, a number of 97 digits.1
A tiny reduction. Reduce 3-SAT, SAT where every clause has three literals, to the independent-set problem: find k vertices with no edge between any two. Build one vertex per literal in each clause. Join the three vertices of a clause, and join every pair of opposite literals (x and not x) from different clauses. The formula is satisfiable exactly when the graph has an independent set of size k, where k is the number of clauses (one vertex per clause).
For the formula (x1 or x2 or x3) and (not x1 or not x2 or x3) and (not x1 or x2 or not x3), the graph has 9 vertices and 15 edges; the formula is satisfiable and a brute-force search finds an independent set of size 3. For an unsatisfiable formula with 4 clauses (it repeats literals inside clauses, a valid but degenerate 3-SAT instance kept small on purpose) the graph has 12 vertices and 32 edges, and no independent set of size 4 exists.1 The reduction builds the graph in polynomial time, which is what the proof needs.
| Quantity | Computed value |
|---|---|
| Assignments, 20 variables | 1,048,576 |
| Time at one billion checks per second (illustrative), 40 variables | about 18.3 minutes |
| Time, 60 variables | about 36.5 years |
| Ways to choose 100 of 400 | about 2.24 × 10⁹⁶ |
| Reduction graph, satisfiable example | 9 vertices, 15 edges |
| Reduction graph, unsatisfiable example | 12 vertices, 32 edges |
Text description of the diagram
- A formula with n variables has 2 to the power n assignments.
- The base-10 logarithm of the count is 6.02 at 20 variables, 12.04 at 40 and 18.06 at 60.
The chart plots the base-10 logarithm of the assignment count: 6.02 at 20 variables, 12.04 at 40 and 18.06 at 60.1
Trade-offs and edge cases
Small changes can flip the difficulty. Wikipedia's NP-completeness article notes there is often only a small difference between a problem in P and an NP-complete one: 3-satisfiability stays NP-complete, while the slightly more restricted 2-satisfiability is in P (Aspvall, Plass and Tarjan, 1979, give a linear-time algorithm). So before declaring a problem hard, check whether your input has the easy structure.
NP-hard is wider than NP-complete. NP-complete needs membership in NP and is a statement about decision problems. Erickson adds that many-one reductions apply only to decision problems, while the more general Cook reductions cover other problem types, and every Karp reduction is a Cook reduction but not the reverse (a Cook reduction may call the solver many times; a Karp reduction converts one instance once). That is why optimization problems are usually called NP-hard, with a decision version proved NP-complete.
Hardness is about worst-case inputs of growing size, not every instance. Real inputs are often small or structured, and exact search with pruning, approximation or heuristics can work well. Compare problems with a clean polynomial answer, like k closest points to the origin or subarray sum equals k: there a better algorithm exists, so the work is finding it. More hardware such as parallel processing divides running time by at most the number of processors; it does not change an exponential growth rate.
Text description of the diagram
- P is the class of problems solved in polynomial time and NP is the class checked in polynomial time.
- NP-complete problems are NP-hard and in NP, while NP-hard problems need not be in NP.
- 2-SAT is in P and 3-SAT is NP-complete.
How to answer it in an interview
What does it mean for a problem to be NP-complete, and what do you do when you meet one?
NP-complete means two things: the problem is in NP, so a proposed answer can be checked in polynomial time, and it is NP-hard, so every NP problem reduces to it. A fast algorithm for one would give a fast algorithm for all, and none is known. When I meet one, I name it, then offer a route: exact search with pruning or dynamic programming for small inputs, an approximation, or a heuristic. I also check whether the input has structure, since 2-SAT is easy while 3-SAT is not.
The spoken structure: define both halves, say what it implies, then give the practical plan. Mention that proofs reduce from a known hard problem to the new one if asked how hardness is shown.
Common mistakes
- "NP means non-polynomial." (wrong) NP stands for nondeterministic polynomial and means polynomial-time checkable. (right) "NP problems have polynomial-time verifiers."
- "NP-complete means impossible to solve." (wrong) Small or structured instances are often solved routinely. (right) "No polynomial-time algorithm for all inputs is known, so I use exact search on small inputs, approximation or heuristics."
- "NP-hard and NP-complete are the same." (wrong) NP-hard problems need not be in NP. (right) "NP-complete is NP-hard and in NP."
- "To prove X is hard, reduce X to a known hard problem." (wrong) That shows X is no harder than it. (right) "I reduce the known NP-complete problem to X, and show X is in NP."
- "NP-complete means exponential time." (wrong) The class is defined by verification and reductions, and P versus NP is open per the Clay Mathematics Institute. (right) "It is believed to need super-polynomial time, but that is unproved."
Follow-up questions
What is the difference between NP-hard and NP-complete?
NP-hard means every NP problem reduces to it. NP-complete means NP-hard and also in NP, so NP-complete problems are the hardest problems inside NP, while NP-hard problems can lie outside it.
Does NP-complete mean a problem takes exponential time?
No. NP-complete is defined by checkability and reductions, not by a measured running time. Exponential time is the best known behavior for the general case, but a polynomial-time algorithm has not been ruled out.
Why do you reduce the known problem to the new one?
Because a fast solver for the new problem then gives a fast solver for the known hard one, so the new problem cannot be easy unless P equals NP. Reducing the other way proves nothing about hardness.
Is 2-SAT NP-complete?
No, 2-satisfiability is in P (linear-time algorithm by Aspvall, Plass and Tarjan, 1979; also Wikipedia's NP-completeness summary), while 3-satisfiability is NP-complete. This pair is the standard example of a small restriction changing difficulty.
What do you do in an interview when a problem is NP-complete?
Say so, and say what it implies: no known polynomial algorithm for every input. Then propose exact search for small sizes, an approximation or a heuristic, and ask about input size and structure. See the coding interview method for how to frame trade-offs; for ordering tasks with dependencies, topological sort runs in linear time; for overlapping time slots, merge intervals is a sort and a sweep.
- NP-complete means in NP and NP-hard: easy to check, and everything in NP reduces to it.
- NP stands for nondeterministic polynomial, not "non-polynomial".
- To prove X NP-complete, show a polynomial-time verifier and reduce a known NP-complete problem to X.
- NP-complete does not mean unsolvable or proved exponential; P versus NP is open.
- In an interview, name the class, then offer exact search for small inputs, approximation or a heuristic.
Sources
- Algorithms Lecture 21: NP-Hard Problems (CS 473) — University of Illinois (Jeff Erickson), 1 Jan 2010
- Reducibility Among Combinatorial Problems — Karp (1972), in Complexity of Computer Computations, 1 Jan 1972
- The complexity of theorem-proving procedures — Cook (1971), ACM Symposium on Theory of Computing, 1 Jan 1971
- A linear-time algorithm for testing the truth of certain quantified boolean formulas — Aspvall, Plass and Tarjan (1979), Information Processing Letters 8(3), 1 Jan 1979
- P vs NP — Clay Mathematics Institute, 26 Oct 2026
- Reductions 2 (CSE 421, lecture 26) — University of Washington, 1 Sep 2022
- NP-hardness — Wikipedia, 26 Oct 2026
- NP-completeness (or how to prove that problems are probably hard), COMS21103 — University of Bristol, 26 Oct 2026
- NP-completeness — Wikipedia, 26 Oct 2026
- Karp's 21 NP-complete problems — Wikipedia, 26 Oct 2026
