Design and Analysis of Algorithms

Answer: (ii) all NP complete are NP hard

NP-complete = NP ∩ NP-hard. All NP-complete are NP-hard and in NP; not all NP-hard are NP-complete (some not in NP). So (ii) true, (i) false.

Answer: (ii) Class NP

Explanation:

• P: problems solvable in polynomial time by a deterministic TM.
• NP: problems where a proposed solution (certificate) can be verified in polynomial time by a deterministic TM (equivalently, solvable in polynomial time by a non-deterministic TM). $P \subseteq NP$.
• NP-Hard: at least as hard as any NP problem (every NP problem reduces to it); may not be in NP.
• NP-Complete = NP $\cap$ NP-Hard.
• Undecidable: no TM can solve all instances.

The definition "verifiable in polynomial time by deterministic TM" is exactly NP.

Correct choice: (ii) Class NP

Answer: (iv) All of these

Explanation:

Let $A \le_p B$ denote polynomial-time many-one (Karp) reduction.

• (i) If $A \le_p B$ and $B \in P$ then $A \in P$: True. Compose reduction $f$ (poly-time) with poly-time decider for $B$ → poly-time decider for $A$. Hence $P$ is closed under $\le_p$.

• **(ii) If $A \le_p B$ and $A
  otin P$then$B
  otin P$**: True — contrapositive of (i). If$B$were in$P$, (i) would put$A$in$P$, contradiction.

• (iii) If $A \le_p B$ and $B \le_p C$ then $A \le_p C$: True — $\le_p$ is transitive; compose the two poly-time reduction functions (polynomial of polynomial is polynomial).

All three are fundamental lemmas used in NP-completeness proofs.

Correct choice: (iv) All of these

Answer: (iii) Polynomial-time reduction from a known NP-complete problem

Explanation:

To prove $L$ is NP-complete you must show:

1. $L \in NP$ (verifiable in polytime), and
2. $L$ is NP-hard: pick a known NP-complete problem $L_0$ (e.g., 3-SAT) and give a polynomial-time reduction $L_0 \le_p L$.

By transitivity of $\le_p$, hardness of $L_0$ transfers to $L$. Subsequent proofs often use Cook's theorem (SAT is NP-complete) as base.

Divide-and-conquer / DP / space calculation do not establish NP-hardness.

Correct choice: (iii)

Answer: (i) $P$ is a subset of $NP$

Explanation:

• $P \subseteq NP$ and it is unknown whether $P = NP$ (Clay Millennium problem).
• Every problem solvable in polytime (P) is also verifiable in polytime (NP) — just solve and check.
• Converse $NP \subseteq P$ would imply $P=NP$, unproven.
• $P$ and $NP$ are not disjoint; $P \cap NP = P$.

Venn: $P \subseteq NP$, $NP$-Complete $\subset NP$, $NP$-Hard ⊇ $NP$-Complete (some outside $NP$).

Correct choice: (i)

Answer: (iii) PSPACE

Explanation:

• QBF (Quantified Boolean Formula): given $\exists x_1 \forall x_2 \exists x_3 \dots \phi(x_1,\dots,x_n)$, is it true? It extends SAT with quantifiers.
• QBF is PSPACE-complete (Stockmeyer-Meyer 1973). SAT is NP-complete; QBF with unbounded alternation captures polynomial-space computation.
• Complete for PSPACE under polytime reductions → canonical PSPACE-complete problem.
• NP is $\exists$-only; co-NP is $\forall$-only; PSPACE allows both via alternation.

Correct choice: (iii) PSPACE

Cook's Theorem (1971) — SAT is NP-Complete

Statement:
The Boolean Satisfiability problem (SAT) — given a Boolean formula $\phi$ in CNF, is there an assignment making $\phi$ true? — is NP-complete.

More precisely Cook proved CNF-SAT is NP-complete; Levin independently proved general SAT. Hence 3-SAT is also NP-complete.

Proof Idea

Must show (1) SAT $\in$ NP and (2) SAT is NP-hard: every $L \in$ NP polytime-reduces to SAT.

1. SAT $\in$ NP: certificate = satisfying assignment, verifier checks formula in polytime.

2. Every NP language reduces to SAT:

   • Let $L \in$ NP decided by nondeterministic TM $M$ in time $p(n)$ (polynomial).
   • For input $x$, $|x|=n$, construct Boolean formula $\phi_x$ that encodes the entire computation tableau of $M$ on $x$: variables represent tape cells, head position, state at each time step $t=0..p(n)$.
   • Add clauses enforcing: initial configuration = $x$, each step follows $M$'s transition relation, and final state is accepting.
   • $\phi_x$ is satisfiable iff there exists an accepting computation path of $M$ on $x$.
   • Size of $\phi_x$ is $O(p(n)^2)$ — polynomial.
   • Conversion $x \mapsto \phi_x$ is deterministic polytime.
     Hence $x \in L \iff \phi_x \in$ SAT → $L \le_p$ SAT.

Significance

• First NP-complete problem — seeds all other NP-completeness proofs by reduction from SAT.
• Implies $P = NP \iff$ SAT $\in$ P.
• Foundations of complexity theory; Karp's 1972 paper reduced SAT to 21 other combinatorial problems (Clique, Vertex Cover, Hamiltonian Cycle), establishing NP-completeness as pervasive.

Corollary

3-SAT (each clause has exactly 3 literals) remains NP-complete via simple reduction from SAT (splitting long clauses with auxiliary variables).

NP-Hard vs NP-Completeness

Aspect	NP-Hard	NP-Complete
Definition	Problem $H$ is NP-hard if every $L\in$ NP reduces to $H$ in polytime: $\forall L\in$ NP, $L\le_p H$. No requirement that $H\in$ NP.	$C$ is NP-complete iff $C$ is both NP-hard and $C\in$ NP. So NP-C = NP ∩ NP-hard.
Verifiable?	Not necessarily verifiable in polytime; may be harder than NP (e.g., Halting, undecidable problems are NP-hard).	Yes, must be verifiable in polytime (certificate check $O(n^k)$).
Examples	Halting Problem, 3-SAT optimization version, TSP optimization; also any NP-complete problem is NP-hard.	Decision versions: SAT, 3-SAT, Clique decision, Vertex Cover decision, Hamiltonian Cycle, Subset Sum decision, TSP decision (is there tour ≤K?).
Reduction direction	To prove NP-hard: reduce known NP-hard/NP-complete $L_0 \le_p H$.	To prove NP-complete: prove (1) $C\in$ NP and (2) $C$ NP-hard (reduce known NP-complete to $C$).
Solvability	If NP-hard problem in P → P=NP, but converse not. NP-hard outside NP cannot be in NP regardless of P vs NP.	If any NP-complete in P → P=NP → all NP problems polytime.
Optimization vs Decision	Optimization forms often NP-hard but not NP-complete because verification of optimality not polytime (just decision version is NP-complete).	Decision versions with yes/no and polytime verifier.

Venn: $P \subseteq$ NP, NP-Complete ⊂ NP, NP-Hard superset overlapping NP (contains NP-C) and extending outside.

Consequence: Showing new problem NP-complete establishes it is among hardest in NP; showing NP-hard shows at least as hard as NP-complete, possibly harder/undecidable.

Complexity Classes $P$, $NP$, $NP$-Complete, $NP$-Hard — Definitions & Relations

Definitions

• $P$ (Polynomial): Decision problems solvable by deterministic TM in $O(n^k)$ for some $k$. Example: Sorting, MST, Shortest path (non-neg). Tractably solvable.
• $NP$ (Nondeterministic Polynomial): Problems where yes instances have certificate verifiable in polytime by deterministic TM (equivalently solvable by nondet TM in polytime). $P\subseteq NP$. Example: SAT, Hamiltonian Cycle decision, Subset Sum.
• $NP$-Hard: Problem $H$ such that $\forall L\in NP$, $L\le_p H$ (polytime reducible). No need to be in $NP$; at least as hard as hardest in $NP$. Example: Halting Problem, TSP optimization, any NP-complete problem.
• $NP$-Complete: $NP \cap$ $NP$-Hard = hardest problems in $NP$. Formal: $C\in NP$ and $\forall L\in NP$, $L\le_p C$. Cook proved SAT is NP-complete. Example: 3-SAT, Clique, Vertex Cover decision, Hamiltonian Cycle.

Relations

P ⊆ NP   (unknown if equal — Clay Millennium)
NP-Complete ⊂ NP
NP-Complete ⊂ NP-Hard
NP-Hard extends outside NP (includes undecidable)
P = NP  ⇔  some NP-complete ∈ P  ⇔  all NP-complete ∈ P
If any NP-hard problem outside NP is in P, not relevant (still P vs NP open).

Venn diagram: Large oval NP-Hard; inside it smaller oval NP; within NP: P region and NP-Complete ring (NP-Complete = intersection of NP-Hard with NP). Outside NP-Hard? None — NP-Hard superset.

Consequences: Proving new problem $X$ NP-complete shows it is among hardest in $NP$; proving NP-hard shows at least as hard (possibly harder than NP).

$P$, $NP$, $NP$-Hard, $NP$-Complete — Relationship (as in Q22)

Definitions:

• $P$: solvable in polytime deterministic.
• $NP$: verifiable in polytime deterministic (or solvable nondet polytime).
• $NP$-Hard: every $NP$ problem polytime reduces to it ($L\le_p H$ ∀$L$∈$NP$).
• $NP$-Complete: $NP$-Hard ∧ ∈$NP$.

Relations:

• $P \subseteq NP$, unknown equality.
• $NP$-Complete = $NP$ ∩ $NP$-Hard.
• $P = NP$ iff some (equivalently all) $NP$-complete ∈ $P$.
• $NP$-Hard includes undecidable problems outside $NP$ (e.g., Halting) → strictly larger.

Diagram concept: Draw big rectangle of all problems, big oval $NP$-Hard overlapping; inside oval, smaller oval $NP$; inside $NP$, region $P$ and ring $NP$-Complete at hardest edge of $NP$ overlapping $NP$-Hard.

Proving $X$ $NP$-complete: Show $X∈NP$ (certificate verifier) + reduce known $NP$-complete $Y \le_p X$.

Complexity Classes & Cook's Theorem — Summary

(i) $P$, $NP$, $NP$-Complete, $NP$-Hard (as in Q22)

• $P$: polytime solvable deterministic — tractable.
• $NP$: polytime verifiable (nondet polytime). $P\subseteq NP$.
• $NP$-Hard: every $NP$ ≤$_p$ it.
• $NP$-Complete: $NP$-Hard ∩ $NP$ — hardest in $NP$.

(ii) Cook's Theorem

SAT (and 3-SAT) is NP-complete. Statement: For any $L∈NP$ with nondet TM $M$ running in $p(n)$, there is polytime construction $x↦ φ_x$ poly-size CNF such that $x∈L ⇔ φ_x$ satisfiable. See Q86 proof sketch (tableau encoding). Converse SAT∈NP via assignment verifier.

(iii) Why Foundational

• First NP-complete problem — provides base for all NP-completeness reductions (Karp's 21 problems).
• Establishes existence of hardest NP problems; implies $P=NP$ iff SAT∈$P$.
• Launched theory of NP-completeness, guiding algorithm design (choose approximation/heuristic when NP-hard).
• Connects logic, computation, and combinatorics; Levin independently discovered similar (Cook-Levin theorem).
• Practical: SAT solvers despite NP-completeness handle huge instances (industrial use).

Polynomial-Time Reduction & NP-Completeness via 3-SAT → Vertex Cover

(i) Polynomial-Time Reduction

Many-one Karp reduction $A ≤_p B$: deterministic algorithm transforming any instance $x$ of $A$ into instance $f(x)$ of $B$ in time $poly(|x|)$ such that $x∈A ⇔ f(x)∈B$. Implies if $B∈P$ then $A∈P$; transitivity holds; $≤_p$ orders hardness.

(ii) Use to Prove NP-Completeness

To prove $B$ NP-complete: show $B∈NP$ + pick known NP-complete $A$ (e.g., 3-SAT) and show $A ≤_p B$. By transitivity every $NP$ problem reduces to $A$ reduces to $B$ → $B$ NP-hard; with $B∈NP$ → NP-complete.

(iii) Reduction 3-SAT → Vertex Cover (Sketch)

3-SAT: Conjunctive normal form with 3 literals per clause, decide satisfiability.
Vertex Cover decision: Given $G(V,E)$ and integer $k$, is there $C⊆V$, $|C|≤k$ covering all edges?

Construction: Given 3-SAT formula with $n$ vars, $m$ clauses.

• Variable gadget: For each variable $x_i$, create two vertices $x_i$, $\bar x_i$ with edge $(x_i,\bar x_i)$. Cover must pick at least one per gadget (choosing truth assignment).
• Clause gadget: For each clause $C_j = (l_a ∨ l_b ∨ l_c)$, create triangle of 3 vertices $a_j,b_j,c_j$ with edges among them. Cover must pick at least 2 of 3 per triangle.
• Connection edges: Connect each triangle vertex to its literal vertex (e.g., $a_j$ — literal $l_a$'s variable node). This forces covering choice to correspond to satisfying literal.
• Set $k = n + 2m$.

Claim: Formula satisfiable ⇔ graph has vertex cover of size ≤ $k$.

• ⇒ If assignment satisfies, pick per variable the true literal vertex, per clause pick 2 triangle vertices covering clause's false literals (at least one literal true, so the edge to its variable vertex is already covered, allowing to pick the other two triangle vertices).
• ⇐ If cover size $k$, it must use exactly 1 per variable gadget and 2 per clause triangle. Extract assignment from variable vertices in cover; each clause triangle leaves one literal uncovered → that literal's edge must be covered by its variable vertex → that literal true → clause satisfied.

Reduction is polytime ($O(n+m)$ vertices/edges). Since 3-SAT NP-complete → Vertex Cover NP-hard; clearly ∈NP (certificate = cover, verifier checks edges) → NP-complete.