10.4 Computational Complexity: Class P, Class NP, Reductions & NP-Complete Problems

Back to DBMS Notes

📚Module 01Topic 1.1⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition:

In the previous topics, we answered the fundamental question of computability: Can this problem be solved by an algorithm at all? We discovered that problems like the Halting Problem and Post Correspondence Problem are mathematically impossible to solve.

However, in real-world computer science, a second, equally critical barrier exists: tractability. A problem might be decidable, but if the fastest known algorithm requires $2^{1000}$ operations, the universe will experience heat death before the computation finishes. Computational complexity classifies solvable problems by the physical resources—time and memory space—demanded by their optimal algorithms.

🍳 The Everyday Analogy:

Consider a $1000$-piece jigsaw puzzle or a $9 \times 9$ Sudoku grid:

• Solving from Scratch (Class NP): If you are handed an empty Sudoku grid, finding the valid numbers requires exploring an exponential tree of possibilities with frequent dead ends and backtracking. Finding the solution from scratch feels hard.
• Verifying a Completed Solution (Class P): If a friend hands you an already-completed Sudoku grid, verifying whether their solution is correct takes less than 60 seconds: you simply scan each of the 9 rows, 9 columns, and 9 boxes to check for duplicates. Verification is blindingly fast.

This asymmetry between finding a solution and verifying a claimed solution is the heart of the Class P versus Class NP divide.

💻 Bridging to Computer Science

In system architecture, algorithm engineering, and cryptography:

• Class P (Deterministic Polynomial Time): Problems solvable in $O(n^k)$ steps (e.g., Shortest Path via Dijkstra, Sorting via MergeSort, Primality Testing via AKS). These problems scale gracefully with massive datasets and run efficiently on production servers.
• Class NP (Nondeterministic Polynomial Time): Decision problems where any candidate solution ("certificate" or "witness") can be verified by a deterministic algorithm in $O(n^k)$ time.
• The $P \stackrel{?}{=} NP$ Question: If an efficient algorithm exists to verify every valid solution, does an efficient algorithm necessarily exist to find that solution from scratch? This remains the most famous open question in theoretical computer science, carrying a $1,000,000 Millennium Prize.

📑Table of Contents

• ⏱️ Asymptotic Complexity Classes: DTIME, NTIME, DSPACE & NSPACE
  • Time Complexity Classes
  • Space Complexity Classes
• 🧩 Defining Class P vs. Class NP
  • Definition: Polynomial-Time Verifier
  • The P versus NP uestion
• 🔄 Polynomial-Time Reductions (A ≤_p B)
  • The Two Critical Directional Rules of Reductions
• 🏆 NP-Hard & NP-Complete Definitions
• 📜 The Cook-Levin Theorem & Karp's 21 NP-Complete Problems
• 🏭 Real-World Production Context: Engineering with NP-Completeness
• 📐 Numerical Applications & Worked Examples
  • Example 1: Verifier Formulation for the Subset-Sum Problem
  • Example 2: Polynomial-Time Reduction: Vertex Cover to Independent Set
  • Example 3: Complexity Classification of Graph Problems
• 🎯 Exam & Interview Pitfall Check

---

⏱️ Asymptotic Complexity Classes: DTIME, NTIME, DSPACE & NSPACE

We formalize computational resources using multi-tape Turing Machines as the standard reference model.

Time Complexity Classes

Let $t: \mathbb{N} \to \mathbb{N}$ be a function.

1. $\text{DTIME}(t(n))$: The class of all languages decidable by a Deterministic Turing Machine running in time $O(t(n))$ for all inputs of length $n$.
2. $\text{NTIME}(t(n))$: The class of all languages decidable by a Non-Deterministic Turing Machine where every computation branch terminates within $O(t(n))$ steps.

$$\text{P} = \bigcup_{k \ge 1} \text{DTIME}(n^k)$$ $$\text{NP} = \bigcup_{k \ge 1} \text{NTIME}(n^k)$$

Space Complexity Classes

Let $s: \mathbb{N} \to \mathbb{N}$ be a function.

1. $\text{DSPACE}(s(n))$: The class of all languages decidable by a Deterministic Turing Machine that scans at most $O(s(n))$ distinct tape cells.
2. $\text{NSPACE}(s(n))$: The class of all languages decidable by a Non-Deterministic Turing Machine that scans at most $O(s(n))$ distinct tape cells.

$$\text{PSPACE} = \bigcup_{k \ge 1} \text{DSPACE}(n^k)$$ $$\text{NPSPACE} = \bigcup_{k \ge 1} \text{NSPACE}(n^k)$$

Architecture Flow

The Computational Complexity Containment Spectrum

The strict and suspected containment chain linking logarithmic space to exponential time

💾Sub-Linear

Logarithmic Space (L)

Problems solvable with O(log n) read/write workspace (pointers).

→

L ⊆ P

⚡Tractable

Polynomial Time (P)

Efficiently solvable problems: Sorting, Shortest Paths, 2-SAT, Matching.

→

P ⊆ NP

🔍Verifiable

Non-Deterministic Time (NP)

Solutions verifiable in polynomial time: 3-SAT, Clique, Hamiltonian Cycle.

→

NP ⊆ PSPACE

🏛️Intractable

Polynomial Space (PSPACE)

Reversible games and logic: Quantified Boolean Formulas (QBF), Chess, Go.

→

PSPACE ⊆ EXPTIME

🔥Exponential

Exponential Time (EXPTIME)

Problems requiring O(2^(n^k)) time. P ⊊ EXPTIME is mathematically proven.

Savitch's Theorem (1970):
For any space-constructible function $s(n) \ge \log n$:

$$\text{NSPACE}(s(n)) \subseteq \text{DSPACE}(s(n)^2)$$

A direct corollary is that non-deterministic polynomial space collapses into deterministic polynomial space:

$$\text{PSPACE} = \text{NPSPACE}$$

---

🧩 Defining Class P vs. Class NP

To analyze NP with mathematical precision, we use the Polynomial-Time Verifier Definition:

Definition: Polynomial-Time Verifier

A language $L \subseteq \Sigma^*$ is in NP if and only if there exists a deterministic polynomial-time algorithm $V$ (called the Verifier) and a polynomial $p(n)$ such that:

$$w \in L \iff \exists c \in \Sigma^* \text{ with } |c| \le p(|w|) \text{ such that } V(w, c) = \text{ACCEPT}$$

• The string $c$ is called the certificate or witness.
• If $w \in L$, there exists at least one concise certificate that proves it to $V$ in polynomial time.
• If $w \notin L$, no certificate $c$—no matter how clever or deceptive—can trick $V$ into accepting.

Class P vs. Class NP: The Solvability vs. Verifiability Boundary

Contrast the computational mechanisms of deterministic solution search vs certificate verification

Class P

Efficient Solvability

⚡

Dominant Architecture / DomainDeterministic Polynomial Time (DTIME(n^k))

• •A deterministic algorithm finds the correct YES/NO answer directly in O(n^k) steps.
• •Zero guessing or certificate required.
• •Closed under complementation: P = co-P.
• •Examples: Minimum Spanning Tree (Kruskal/Prim), GCD (Euclid), Linear Programming (Interior Point).

"Problems where an algorithmic path to the solution is directly computable."

Class NP

Efficient Verifiability

🔍

Dominant Architecture / DomainPolynomial-Time Witness Verification

• •A deterministic verifier checks a proposed certificate in O(n^k) steps.
• •Finding the certificate might require exponential brute force over all candidates.
• •Suspected to NOT be closed under complementation: NP ≠ co-NP.
• •Examples: 3-SAT, Traveling Salesperson (Decision), Graph Coloring, Subset Sum.

"Problems where verifying a proposed answer is easy, even if finding it is hard."

The P versus NP uestion

Because any deterministic algorithm running in time $O(n^k)$ can verify its own solution in polynomial time (by simply ignoring the certificate and computing the answer directly), we have:

$$\text{P} \subseteq \text{NP}$$

The central open question in modern science is whether the reverse holds:

$$\text{P} \stackrel{?}{=} \text{NP}$$

Most computer scientists strongly believe that $\text{P} \ne \text{NP}$. If $\text{P} = \text{NP}$, every problem whose solution can be easily checked could also be solved just as easily. This would break modern asymmetric cryptography (RSA, ECC), automate mathematical theorem proving, and revolutionize drug discovery.

---

🔄 Polynomial-Time Reductions (A ≤_p B)

To rank the relative difficulty of computational problems, we use Karp Reductions (Polynomial-Time Many-One Reductions):

Definition (Polynomial-Time Reduction):
A language $A \subseteq \Sigma^*$ is polynomial-time reducible to a language $B \subseteq \Gamma^*$ (denoted $A \le_p B$) if there exists a function $f: \Sigma^* \to \Gamma^*$ such that:

1. $f$ is computable by a Deterministic Turing Machine in polynomial time $O(n^k)$.
2. For every input string $w \in \Sigma^*$:

$$w \in A \iff f(w) \in B$$

Architecture Flow

The Mechanics of a Polynomial-Time Reduction (A ≤p B)

How an instance of Problem A is transformed into an instance of Problem B

📥Input A

Instance w of Problem A

Arbitrary input string w whose membership in language A is unknown.

→

f(w) in O(n^k)

⚙️Transformation

Polynomial Reducer Engine

Deterministic transformation converts instance w into candidate instance f(w).

→

Maps to B

📦Black Box

Solver for Problem B

Executes solver on f(w). Solver outputs YES if and only if w belongs to A.

The Two Critical Directional Rules of Reductions

Whenever $A \le_p B$:

1. Tractability Transfers Upwards:

$$(A \le_p B \land B \in \text{P}) \implies A \in \text{P}$$

If Problem $B$ is easy, then Problem $A$ must also be easy. 2. Hardness Transfers Downwards:

$$(A \le_p B \land A \notin \text{P}) \implies B \notin \text{P}$$

If Problem $A$ is hard, then Problem $B$ must be at least as hard.

---

🏆 NP-Hard & NP-Complete Definitions

Using polynomial-time reductions, we can define the hardest problems in the entire class NP:

The Structural Hierarchy of Complexity Classes (Assuming P ≠ NP)

The relationship between Class P, Class NP, NP-Complete, and NP-Hard

NP-Hard

At Least as Hard as Every Problem in NP

🔥

A language H is NP-Hard if every language L in NP reduces to H in polynomial time (∀L ∈ NP, L ≤p H). NP-Hard problems do NOT need to be in NP, and many are undecidable (e.g., the Halting Problem is NP-Hard!).

Halting ProblemExact TSP OptimizationGeneral QBFPost Correspondence Problem

↓Intersection with NP Defines NP-Complete

NP-Complete

The Hardest Problems Inside Class NP

🏆

A language X is NP-Complete if: (1) X ∈ NP, and (2) X is NP-Hard. If ANY single NP-Complete problem can be solved in polynomial time, then P = NP.

3-SATVertex CoverCliqueHamiltonian CycleSubset SumGraph 3-Coloring

↓Contains Tractable Core

Class P

Tractable Deterministic Polynomial-Time Core

⚡

Problems solvable in deterministic O(n^k) time. Contained strictly inside NP assuming P ≠ NP.

2-SATShortest PathEulerian CircuitMinimum Spanning TreeMatrix Multiplication

---

📜 The Cook-Levin Theorem & Karp's 21 NP-Complete Problems

How do you prove the very first problem is NP-Hard when you have no existing NP-Hard problems to reduce from?

The Cook-Levin Theorem (1971):
The Boolean Satisfiability Problem (SAT) is NP-Complete.

Proof Sketch:
Stephen Cook and Leonid Levin independently proved that for any arbitrary language $L \in \text{NP}$ and input string $w$, the complete execution history of the polynomial-time Non-Deterministic Turing Machine $M$ accepting $w$ can be encoded as a single giant Boolean formula $\Phi_{M, w}$ in Conjunctive Normal Form (CNF):

• Variables encode tape cell contents, head positions, and state transitions across $p(n)$ time steps.
• The formula $\Phi_{M, w}$ has size polynomial in $|w|$ ($O(p(n)^2)$).
• $\Phi_{M, w}$ is satisfiable if and only if there exists a valid sequence of non-deterministic transitions leading to an accepting state.
• Therefore, $w \in L \iff \Phi_{M, w} \in \text{SAT}$, proving $L \le_p \text{SAT}$ for all $L \in \text{NP}$.

Once SAT was established as the root NP-Complete problem, Richard Karp (1972) established a tree of polynomial-time reductions showing that 21 foundational combinatorial problems are all NP-Complete:

Canonical NP-Complete Problems vs. Their Tractable P Counterparts

Small variations in problem constraints that cause the complexity to jump from P to NP-Complete

🔀

Boolean Satisfiability

2-SAT vs 3-SAT

• 2-SAT (clauses with 2 literals): In P via Strongly Connected Components in an implication graph (O(V + E)).
• 3-SAT (clauses with 3 literals): NP-Complete via Cook-Levin theorem reduction.

🕸️

Graph Traversal

Eulerian vs Hamiltonian

• Eulerian Circuit (visit every edge once): In P (check if all vertices have even degree in O(V + E)).
• Hamiltonian Cycle (visit every vertex once): NP-Complete.

📏

Path Optimization

Shortest vs Longest Path

• Shortest Path: In P via Dijkstra's algorithm (O(E + V log V)) or Bellman-Ford.
• Longest Simple Path (between two vertices without cycles): NP-Complete.

🎨

Graph Coloring

2-Color vs 3-Color

• 2-Colorability (Bipartite Graph): In P via simple 2-color BFS/DFS in O(V + E).
• 3-Colorability: NP-Complete even for planar graphs with maximum degree 4.

---

🏭 Real-World Production Context: Engineering with NP-Completeness

Software engineers encounter NP-Complete problems daily in large-scale infrastructure. When a problem is proven NP-Complete, you do not waste months trying to find an exact polynomial-time algorithm. Instead, production systems adopt four proven engineering strategies:

1. SAT/SMT Solvers in Formal Verification:
   • Modern Boolean SAT solvers (Z3, CaDiCaL, CVC5) use Conflict-Driven Clause Learning (CDCL). Despite the theoretical exponential worst-case of 3-SAT, production solvers solve instances with millions of variables in seconds.
   • Amazon Web Services (AWS) uses SMT solvers (Z3) to verify that IAM security policies and VPC routing tables contain zero unauthorized data exposure paths.
2. Compiler Register Allocation via Graph Coloring:
   • Mapping an arbitrary number of program variables to a finite set of $k$ CPU registers (e.g., 16 x86-64 registers) is isomorphic to the $k$-Graph Coloring problem (NP-Complete).
   • Compilers like GCC and LLVM use Chaitin's heuristic algorithm: build an interference graph, simplify vertices of degree $< k$, and spill variables to RAM only when coloring fails.
3. Approximation Algorithms for Logistics:
   • The Traveling Salesperson Problem (TSP) and Bin Packing govern route optimization for shipping fleets (UPS, Amazon).
   • Instead of searching for the exact optimum, routing engines use polynomial-time approximation schemes (e.g., Christofides' 1.5-approximation algorithm for Metric TSP) or meta-heuristics (Simulated Annealing, Genetic Algorithms).
4. Cryptographic Asymmetry:
   • Public-key cryptography (RSA, Diffie-Hellman, Elliptic Curves) relies fundamentally on one-way computational asymmetry.
   • Multiplying two 2048-bit primes takes microseconds (in Class P). Factoring the resulting 4096-bit composite number requires superpolynomial time with classical algorithms.

---

📐 Numerical Applications & Worked Examples

Example 1: Verifier Formulation for the Subset-Sum Problem

Problem Statement:
The SUBSET-SUM decision problem is defined as follows:
Given a finite set of integers $S = \{s_1, s_2, \dots, s_n\}$ and an integer target $T$, does there exist a subset $S' \subseteq S$ such that:

$$\sum_{x \in S'} x = T$$

Formulate a formal polynomial-time Verifier algorithm $V(I, c)$ to prove that $\text{SUBSET-SUM} \in \text{NP}$. Specify the structure of the certificate $c$, its size bound, and the exact asymptotic runtime of the verifier.

Step-by-Step Solution:

• Step 1: Certificate Structure and Size Bound:
  • Let the instance be $I = (S, T)$, where $n = |S|$ and each integer $s_i$ is encoded in binary using at most $b$ bits. The total input size is $|I| = O(n \cdot b)$.
  • A candidate certificate $c$ is a binary bitmask of length $n$:

$$c = (x_1, x_2, \dots, x_n) \in \{0, 1\}^n$$

where $x_i = 1$ indicates that $s_i \in S'$, and $x_i = 0$ indicates $s_i \notin S'$.

• The size of the certificate is $|c| = n \le |I|$, which is strictly bounded by a linear polynomial $p(|I|)$.

• Step 2: Deterministic Verifier Algorithm $V(I, c)$:

  def verify_subset_sum(S, T, c):
      # Step 2a: Check certificate length
      if len(c) != len(S):
          return "REJECT"
      
      # Step 2b: Accumulate the sum of selected elements
      running_sum = 0
      for i in range(len(S)):
          if c[i] == 1:
              running_sum += S[i]
      
      # Step 2c: Compare against target
      if running_sum == T:
          return "ACCEPT"
      else:
          return "REJECT"

• Step 3: Verification Correctness:

  • If $(S, T) \in \text{SUBSET-SUM}$, there exists a valid subset summing to $T$. Setting $x_i = 1$ for elements in that subset produces a certificate where $V(I, c)$ accepts.
  • If $(S, T) \notin \text{SUBSET-SUM}$, no subset sums to $T$. Every possible bitmask $c \in \{0, 1\}^n$ results in $\sum x_i s_i \ne T$, causing $V$ to output REJECT.

• Step 4: Complexity Analysis:

  • The loop performs $n$ additions of numbers with at most $b$ bits.
  • Addition of two $b$-bit numbers takes $O(b)$ bit operations.
  • Total verifier runtime is $O(n \cdot b) = O(|I|)$ time, which is strictly deterministic polynomial time.
  • Therefore, $\text{SUBSET-SUM} \in \text{NP}$.

---

Example 2: Polynomial-Time Reduction: Vertex Cover to Independent Set

Problem Statement:
Recall the definitions of two classic graph decision problems:

• VERTEX-COVER: Given an undirected graph $G = (V, E)$ and integer $k$, does there exist a subset $V' \subseteq V$ with $|V'| \le k$ such that every edge $(u, v) \in E$ has at least one endpoint in $V'$?
• INDEPENDENT-SET: Given an undirected graph $G = (V, E)$ and integer $m$, does there exist a subset $S \subseteq V$ with $|S| \ge m$ such that no two vertices in $S$ share an edge in $E$?

Assuming that VERTEX-COVER is known to be NP-Complete, construct a polynomial-time reduction:

$$\text{VERTEX-COVER} \le_p \text{INDEPENDENT-SET}$$

and prove its mathematical correctness.

Step-by-Step Solution:

• Step 1: Construction of the Reduction Function $f$:
  • Given an arbitrary instance of VERTEX-COVER: $(G, k)$ where $G = (V, E)$ with $n = |V|$ vertices.
  • Construct an instance of INDEPENDENT-SET: $(G', m)$ where:

$$G' = G = (V, E) \quad \text{and} \quad m = n - k$$

• The graph remains unchanged, and the target size is computed as $m = |V| - k$.

• This transformation requires only computing $n - k$, which executes in $O(1)$ time (trivially polynomial $O(n)$).

• Step 2: Proof of Correctness ($\implies$ Direction):

  • Suppose $(G, k) \in \text{VERTEX-COVER}$.
  • Then there exists a vertex cover $V' \subseteq V$ with $|V'| \le k$.
  • Consider the complementary set $S = V \setminus V'$.
  • The size of $S$ is:

$$|S| = |V| - |V'| \ge n - k = m$$

• We claim $S$ is an independent set. Suppose for contradiction that $S$ is not independent. Then there exists an edge $(u, v) \in E$ with both $u \in S$ and $v \in S$.

• Since $u \in S$ and $v \in S$, neither $u$ nor $v$ belongs to $V'$.

• But this means edge $(u, v)$ has neither endpoint in $V'$, which contradicts the fact that $V'$ is a valid vertex cover!

• Thus, no such edge can exist in $S$, so $S$ is an independent set of size at least $m$.

• Therefore, $(G', m) \in \text{INDEPENDENT-SET}$.

• Step 3: Proof of Correctness ($\impliedby$ Direction):

  • Suppose $(G', m) \in \text{INDEPENDENT-SET}$.
  • Then there exists an independent set $S \subseteq V$ with $|S| \ge m = n - k$.
  • Consider the complementary set $V' = V \setminus S$.
  • The size of $V'$ is:

$$|V'| = |V| - |S| \le n - (n - k) = k$$

• We claim $V'$ is a vertex cover. Suppose for contradiction that $V'$ is not a vertex cover. Then there exists an edge $(u, v) \in E$ such that neither $u \in V'$ nor $v \in V'$.

• Since neither is in $V'$, both $u$ and $v$ must belong to $S = V \setminus V'$.

• But this means edge $(u, v)$ connects two vertices in $S$, which contradicts the fact that $S$ is an independent set!

• Thus, $V'$ must cover every edge in $E$, and $|V'| \le k$.

• Therefore, $(G, k) \in \text{VERTEX-COVER}$.

• Conclusion:
  Because $(G, k) \in \text{VERTEX-COVER} \iff f(G, k) \in \text{INDEPENDENT-SET}$ and $f$ runs in polynomial time, $\text{VERTEX-COVER} \le_p \text{INDEPENDENT-SET}$. Since VERTEX-COVER is NP-Complete and INDEPENDENT-SET is in NP, INDEPENDENT-SET is also NP-Complete.

---

Example 3: Complexity Classification of Graph Problems

Problem Statement:
Classify each of the following four decision problems into exactly one of three categories: Class P, NP-Complete, or Undecidable:

1. Problem $Q_1$: Given an undirected graph $G$, does $G$ contain a simple cycle of length at least 3?
2. Problem $Q_2$: Given a Boolean formula in 3-CNF, does there exist a truth assignment that makes at least two literals true in every clause?
3. Problem $Q_3$: Given an arbitrary Turing Machine $M$, does there exist an input $w$ on which $M$ visits at most $|w|^2$ tape cells?
4. Problem $Q_4$: Given an undirected graph $G$ and an integer $k$, does $G$ contain a clique of size at least $k$?

Step-by-Step Solution:

• Analysis of $Q_1$ (Simple Cycle in Graph):

  • An undirected graph with $V$ vertices contains a cycle if and only if a Depth-First Search (DFS) encounters a back-edge to an ancestor (excluding the immediate parent).
  • DFS runs in $O(V + E)$ time.
  • If $E \ge V$, the graph is guaranteed to contain a cycle by the Pigeonhole Principle.
  • Because an algorithm exists that decides the problem in linear time $O(V + E)$, $Q_1$ belongs to Class P.

• Analysis of $Q_2$ (Not-All-Equal 3-SAT / 2-True SAT):

  • Requiring at least two literals true in every 3-literal clause is equivalent to requiring that not all literals are false and not all are true (the classic NAE-3-SAT problem).
  • NAE-3-SAT is one of Karp's foundational NP-Complete problems, established by reduction from standard 3-SAT.
  • A candidate truth assignment can be verified in linear time $O(m)$ for $m$ clauses, placing it in NP.
  • Therefore, $Q_2$ is NP-Complete.

• Analysis of $Q_3$ (TM tape usage bound):

  • This asks whether there exists an input on which a general Turing Machine $M$ respects a polynomial space bound.
  • This is a non-trivial property of the computational behavior of Turing machines.
  • By reduction from the Halting Problem (or Rice's Theorem on computation traces), determining whether an unconstrained TM restricts its tape head within a bound is undecidable.
  • Therefore, $Q_3$ is Undecidable.

• Analysis of $Q_4$ (CLIQUE of size $\ge k$):

  • A candidate clique of $k$ vertices can be verified in $O(k^2) = O(V^2)$ time by checking whether all $\binom{k}{2}$ vertex pairs are connected by edges in $E$.
  • Thus, $\text{CLIQUE} \in \text{NP}$.
  • Karp (1972) proved that 3-SAT reduces to CLIQUE in polynomial time ($3\text{-SAT} \le_p \text{CLIQUE}$).
  • Therefore, $Q_4$ is NP-Complete.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

1. Can an undecidable problem be NP-Hard?

   • Answer: YES! A problem $H$ is NP-Hard if every problem in NP reduces to $H$ in polynomial time ($L \le_p H$ for all $L \in \text{NP}$). There is no requirement that $H$ must be in NP or even decidable! For example, the Halting Problem ($L_{HP}$) is provably NP-Hard because any NP problem can be decided by an exponential-time TM, which can be encoded into a halting question. However, $L_{HP}$ is not NP-Complete because $L_{HP} \notin \text{NP}$.

2. If someone proves that an NP-Complete problem can be solved in $O(n^{\log n})$ time, does that prove $P = NP$?

   • Answer: NO. $O(n^{\log n})$ is quasi-polynomial time, not polynomial time ($O(n^k)$ for a constant $k$). Proving an NP-Complete problem runs in $O(n^{\log n})$ would shatter the Exponential Time Hypothesis (which asserts NP-Complete problems require $2^{\Omega(n)}$), but it would NOT prove $P = NP$.

Common Interview Traps

• Trap: Reversing the Reduction Direction:
  • To prove a new problem $B$ is NP-Hard, you must reduce from an existing NP-Hard problem $A$ to $B$ ($A \le_p B$). If you reduce from $B$ to $A$ ($B \le_p A$), you have only proved that $B$ is no harder than $A$—you have proved nothing about $B$'s hardness!
• Trap: Confusing NP with "Non-Polynomial":
  • "NP" does NOT stand for "Not Polynomial"! It stands for Non-deterministic Polynomial time. Every problem in P is also in NP ($\text{P} \subseteq \text{NP}$).
• Trap: Assuming 2-SAT and 3-SAT have Similar Complexity:
  • 2-SAT is in Class P (solvable in $O(V + E)$ linear time using implication graphs and strongly connected components). 3-SAT is NP-Complete. Adding just one literal per clause triggers an exponential phase transition in computational complexity.

---

🗺️View Complete DBMS Roadmap & Syllabus

← Previous Topic10.3 Master Decision & Closure Properties Matrix Across All 4 Chomsky ClassesNext Topic →Theory of Computation: Master Course Index