---
title: "Class P, class NP and NP-complete"
subject: "Theory of Computation"
chapter: 6
key: "semester_3/theory_of_computation:class-p-np-relation"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/class-p-np-relation
site: BCT Engineering
---

# Class P, class NP and NP-complete

Theory of Computation · Chapter 6: Computational Complexity

- Asked in: 2071 Chaitra
- Video: [NP completeness (P, NP and NPC) Polynomial, Non-Polynomial, NP-Complete and NP hard algorithms](https://www.youtube.com/watch?v=19ryrsQIq3o) — Helping Tutorials
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/class-p-np-relation
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-6

## Question

Define class P and class NP problems with example. How do they relate to NP-complete problems?

## Short answer

P: decision problems solvable in polynomial time by a deterministic TM (e.g., shortest path). NP: problems with polynomial-time verifiable certificates (e.g., SAT). NP-complete problems are the hardest in NP; every NP problem reduces to them. P ⊆ NP; if P ≠ NP, NP-complete problems are not in P. If any NP-complete problem is in P, then P=NP.

## Answer

#### Class P
P is the class of decision problems solvable by a **deterministic Turing machine in polynomial time**, i.e. in O(nᵏ) steps for some constant k.

Examples: sorting, shortest path (Dijkstra), minimum spanning tree, searching, primality testing, 2-SAT, and checking whether a graph is connected.

#### Class NP
NP is the class of decision problems solvable by a **non-deterministic Turing machine in polynomial time**. Equivalently, if the answer is "yes", there is a short certificate (proof) that can be **verified in polynomial time** by a deterministic machine.

Examples:
- **SAT:** is there a truth assignment satisfying the formula? (Certificate: the assignment.)
- **Hamiltonian cycle:** does a graph have a cycle through every vertex once? (Certificate: the cycle.)
- **Subset sum, CLIQUE, Vertex cover, TSP (decision version).**

#### Relation of P, NP and NP-complete
- **P ⊆ NP**, since a deterministic TM is a special case of a non-deterministic TM. Whether P = NP is the major open problem.
- A problem is **NP-complete** if it is in NP and every problem in NP reduces to it in polynomial time. NP-complete problems are the hardest problems in NP.
- If P ≠ NP, then NP-complete problems are not in P. If any one NP-complete problem is in P, then P = NP.

```text
   Assuming P ≠ NP:
   ┌─────────────────────────┐
   │ NP                      │
   │   ┌──────┐  ┌────────┐  │
   │   │  P   │  │  NP-   │  │
   │   │      │  │complete│  │
   │   └──────┘  └────────┘  │
   └─────────────────────────┘
```

Examples: SAT and Hamiltonian cycle are NP-complete; sorting is in P; the Cook–Levin theorem proved the first NP-complete problem (SAT).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is class P?
   A. Decision problems solvable by a non-deterministic TM in polynomial time
   B. Decision problems solvable by a deterministic TM in polynomial time, O(n^k)
   C. Problems solvable in exponential time
   D. Problems whose answers can only be checked, not found
   Answer: B. P contains decision problems a deterministic TM solves in O(n^k) steps for some constant k. (Key point: Class P)

2. What is the 'verification' view of NP, using SAT as an example?
   A. A yes answer has a short certificate (a satisfying assignment) checkable in polynomial time
   B. The satisfying assignment must be found in polynomial time by a deterministic machine
   C. A no answer has a short certificate checkable in polynomial time
   D. NP problems can never be solved by any machine
   Answer: A. For a yes instance, a certificate such as a satisfying assignment can be verified in polynomial time by a deterministic machine. (Key point: Class NP and certificates)

3. Why is P ⊆ NP?
   A. Because every NP problem has a polynomial algorithm
   B. Because NP is defined to equal P
   C. Because a deterministic TM is a special case of a non-deterministic TM
   D. Because verification is always harder than solving
   Answer: C. Any polynomial-time deterministic TM is also a non-deterministic TM, so P is contained in NP. Whether P = NP remains open. (Key point: P subset of NP)

4. If P ≠ NP, what holds for NP-complete problems?
   A. They are all in P
   B. They are not in P, and if any one were in P then P = NP
   C. They are outside NP
   D. They are easier than problems in P
   Answer: B. NP-complete problems are the hardest in NP; if one were in P, all NP would be, giving P = NP. (Key point: NP-complete relation)

## Related in Theory of Computation

- [NP-hard and NP-complete problems](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Anp-hard-np-complete) — Theory of Computation, chapter 6, asked 2×