Every problem in P is also in NP because:

If it can be solved in polynomial time, a proposed answer can certainly be verified in polynomial time by simply solving it yourself

No problem in P can ever be verified

A problem is NP-complete if it is:

Both NP-hard and itself a member of NP

The Hamiltonian cycle problem (visit every vertex exactly once) is NP-complete, while the Eulerian circuit problem (traverse every edge exactly once) is in P. This is best explained by:

Euler has a clean degree-parity characterisation with no known analogue for Hamiltonian cycles

The two problems are actually identical

Euler is harder than Hamiltonian

Neither problem can ever be solved

The halting problem is NP-hard but NOT NP-complete because:

It is not even decidable, so it is not itself a member of NP

NP-hard and NP-complete are exact synonyms

It has never been proven hard at all

Which of the following are standard NP-complete problems? (More than one option may be correct.)

Single-source shortest path with non-negative weights

Complexity Theory: P, NP and NP-Completeness

NET's Unit 7 names P and NP class problems, NP-completeness and reducibility as a topic of its own, beyond the asymptotic complexity, design techniques and graph algorithms of the course's Algorithms chapters. This chapter grounds them carefully: like the automata-theory claims in Unit 8, these are precise statements that must never be hand-waved.

The Classes P and NP

P is the class of DECISION problems (yes/no answers) solvable by a deterministic algorithm in worst-case time polynomial in the input size — informally, 'efficiently solvable'. NP is the class of decision problems for which a proposed YES-answer (a CERTIFICATE/witness) can be VERIFIED in polynomial time, even if no polynomial-time algorithm is known to FIND that certificate in the first place. Every problem in P is also in NP (if you can solve it in polynomial time, you can certainly verify a proposed answer in polynomial time by just solving it yourself) — so P ⊆ NP is proven; whether P = NP (whether every efficiently-VERIFIABLE problem is also efficiently-SOLVABLE) is the most famous open problem in computer science, unresolved.

⚠️ NP does NOT stand for 'Non-Polynomial'

This is the single most common misreading. NP stands for NONDETERMINISTIC POLYNOMIAL — a nondeterministic Turing machine that can 'guess' a certificate and verify it in polynomial time, or equivalently (the definition actually used in practice), a class defined by polynomial-time VERIFICATION of a proposed certificate. NP problems are not known to be unsolvable in polynomial time; some of them (all of P) demonstrably ARE solvable in polynomial time. What is open is whether ALL of NP is.

NP-Completeness and Polynomial-Time Reducibility

A problem X is NP-hard if every problem in NP can be POLYNOMIAL-TIME REDUCED to X — informally, X is 'at least as hard as everything in NP', since a polynomial-time algorithm for X would give a polynomial-time algorithm for every NP problem. A problem X is NP-complete if it is BOTH NP-hard AND itself in NP — the 'hardest problems that are still verifiable', and it is exactly these that a polynomial-time algorithm for even ONE of them would prove P = NP for ALL of them, since NP-complete problems are all polynomial-time reducible to each other. Cook's theorem (1971) proved the FIRST NP-complete problem — Boolean SATISFIABILITY (SAT) — establishing that NP-complete problems exist at all; every subsequent NP-completeness proof reduces a KNOWN NP-complete problem to the new candidate (or the candidate to a known one), building outward from that single anchor.

Standard NP-complete problems and how they relate
Problem	Statement
SAT / 3-SAT	Given a Boolean formula (in 3-SAT: in conjunctive normal form with 3 literals per clause), does some assignment of true/false to its variables make the whole formula true?
Vertex Cover	Does a graph have a set of at most k vertices touching every edge?
Hamiltonian Cycle	Does a graph have a cycle visiting every vertex exactly once?
0/1 Knapsack (decision version)	Can items be chosen within a weight limit to reach at least a target value V?

Recognising NP-Completeness from the Shape of the Question

🧠 Recognise NP-completeness from the shape of the question, not the topic

Many NP-complete problems have EASY, polynomial-time cousins that sound almost identical — the trap is confusing the two. The shortest-path problem is in P (Dijkstra, for non-negative weights); the LONGEST simple path problem is NP-hard. The Eulerian circuit problem (every EDGE once) is in P, decidable by a simple degree-parity check; the Hamiltonian cycle problem (every VERTEX once) is NP-complete, with no known parity-style shortcut. 2-SAT (at most 2 literals per clause) is in P; 3-SAT is NP-complete. Reading which exact variant is asked, not just the topic area, is what separates these questions.

NP-Hard Without Being NP-Complete, and Tractable vs Intractable

A problem can be NP-hard WITHOUT being NP-complete if it is not itself in NP — usually because it is not even a decision problem, or because verifying a proposed solution is not known to be possible in polynomial time. The HALTING PROBLEM (covered in Unit 8's Theory of Computation material) is NP-hard by this definition but is not NP-complete, because it is not even DECIDABLE at all — no algorithm, polynomial or otherwise, solves it in general, so it is strictly harder than anything in NP rather than merely as hard as the hardest NP problems. The TRAVELLING SALESMAN PROBLEM in its OPTIMISATION form ('find the shortest tour') is NP-hard but, being an optimisation rather than decision problem, is not itself a member of NP — its DECISION version ('is there a tour of length ≤ k?') is what is actually NP-complete.

Tractable informally means 'solvable in polynomial time' (P); intractable informally means 'no known polynomial-time algorithm exists' — NP-complete problems are the standard examples of (believed) intractable problems, since a polynomial-time algorithm for any one would collapse P and NP together.
In practice, an NP-complete problem is not abandoned once identified — exponential-worst-case algorithms (branch-and-bound, backtracking with strong pruning) can still be fast enough on the actual instances that arise in practice, and approximation algorithms (covered in the next chapter) trade exactness for a provably-bounded-away-from-optimal answer computable in polynomial time.

Key takeaways

P is efficiently solvable; NP is efficiently verifiable (a proposed certificate checked in polynomial time) — P ⊆ NP is proven, P = NP is open.
NP stands for 'Nondeterministic Polynomial', not 'non-polynomial' — the standard misreading.
A problem is NP-complete if it is NP-hard AND in NP; NP-complete problems are all polynomial-time reducible to each other, so a fast algorithm for one solves them all.
Many NP-complete problems have easy polynomial cousins that sound similar (Hamiltonian vs Euler cycle, 3-SAT vs 2-SAT, shortest vs longest path) — read the exact variant.
The halting problem is NP-hard but not NP-complete because it is not even decidable; TSP's optimisation form is NP-hard but not itself in NP, unlike its decision form.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

NP stands for:
1. Nondeterministic Polynomial
2. Non-Polynomial
3. Never Provable
4. New Programming
Show answer
Answer: A — Nondeterministic Polynomial
NP is Nondeterministic Polynomial — the class of problems whose proposed yes-certificates are verifiable in polynomial time — not a claim that these problems require more than polynomial time.
Every problem in P is also in NP because:
1. If it can be solved in polynomial time, a proposed answer can certainly be verified in polynomial time by simply solving it yourself
2. P and NP are unrelated sets
3. NP is a subset of P
4. No problem in P can ever be verified
Show answer
Answer: A — If it can be solved in polynomial time, a proposed answer can certainly be verified in polynomial time by simply solving it yourself
Solving a problem yourself in polynomial time is itself a polynomial-time way to verify any proposed answer to it, which is exactly the argument that establishes P ⊆ NP.
A problem is NP-complete if it is:
1. Both NP-hard and itself a member of NP
2. NP-hard but never in NP
3. In P but never in NP
4. Undecidable
Show answer
Answer: A — Both NP-hard and itself a member of NP
NP-completeness requires both conditions together — being at least as hard as every NP problem AND being itself verifiable in polynomial time — which is why NP-complete problems are all polynomial-time reducible to each other.
The Hamiltonian cycle problem (visit every vertex exactly once) is NP-complete, while the Eulerian circuit problem (traverse every edge exactly once) is in P. This is best explained by:
1. Euler has a clean degree-parity characterisation with no known analogue for Hamiltonian cycles
2. The two problems are actually identical
3. Euler is harder than Hamiltonian
4. Neither problem can ever be solved
Show answer
Answer: A — Euler has a clean degree-parity characterisation with no known analogue for Hamiltonian cycles
A closed Euler circuit is decidable in linear time purely by checking that every vertex has even degree; no comparably simple, efficiently-checkable characterisation is known for Hamiltonian cycles, which is exactly the source of the two problems' very different complexity.
The halting problem is NP-hard but NOT NP-complete because:
1. It is not even decidable, so it is not itself a member of NP
2. It is actually in P
3. NP-hard and NP-complete are exact synonyms
4. It has never been proven hard at all
Show answer
Answer: A — It is not even decidable, so it is not itself a member of NP
NP-completeness requires membership in NP as well as NP-hardness; since no algorithm at all (polynomial or otherwise) decides the halting problem, it cannot be verified in polynomial time either, so it fails the NP-membership half of the definition.
Which of the following are standard NP-complete problems? (More than one option may be correct.)
1. 3-SAT
2. Vertex Cover
3. Hamiltonian Cycle
4. Single-source shortest path with non-negative weights
Show answer
Answer: A — 3-SAT; B — Vertex Cover; C — Hamiltonian Cycle
3-SAT, Vertex Cover and Hamiltonian Cycle are standard, textbook NP-complete problems; single-source shortest path with non-negative weights is in P, solved efficiently by Dijkstra's algorithm.
Name the theorem (1971) that established the FIRST known NP-complete problem, namely Boolean satisfiability (SAT).
Numerical answer — type the value.
Show answer
Answer: Cook's theorem
Cook's theorem (independently also proved by Levin, hence often called the Cook-Levin theorem) proved SAT NP-complete directly from the definition of NP, giving every later NP-completeness proof its starting anchor for reduction.
The travelling salesman problem in its optimisation form ('find the shortest tour') is:
1. NP-hard, but not itself a member of NP since it is not a decision problem
2. In P
3. Decidable in constant time
4. Identical to its own decision version
Show answer
Answer: A — NP-hard, but not itself a member of NP since it is not a decision problem
Only the DECISION version ('is there a tour of length ≤ k?') can be a member of NP, since NP membership requires a yes/no certificate to verify; the optimisation version is NP-hard (at least as hard) but not itself classified inside NP.