Question bank — NP-complete problems — 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP, Subset Sum

False. NP just means a proposed answer is checkable in polynomial time. Every problem in P is also in NP (checking is at least as easy as re-solving), so "in NP" says nothing about being hard.

False. No polynomial algorithm is known, but none is proven impossible either — that unresolved gap is exactly the P vs NP question.

True. Vertex Cover is NP-complete, so every NP problem — including TSP — reduces to it in poly time; a fast solver for one collapses the whole class into P.

False, and this is the classic direction error. You reduce the known-hard $A$ into $B$ ($A{\le }_{p}B$), feeding the monster to $B$. Reducing $B$ into $A$ only shows $B$ is no harder than $A$.

False. The target $t$ is written in $\log t$ bits, so $t$ can be exponential in the input length. The DP is pseudo-polynomial, not polynomial — see Dynamic Programming — Subset Sum / Knapsack.

True. An independent set has no internal edges in $G$; flipping every edge (forming $\bar{G}$) turns all those non-edges into edges, making the same vertices pairwise adjacent — a clique.

True. Any edge with both endpoints in $I$ would violate independence, so every edge has at least one endpoint outside $I$ — exactly the vertex-cover condition. See Graph Theory — Cliques and Independent Sets.

False. Cook–Levin proves SAT is NP-complete directly from the Turing-machine definition — every NP problem reduces to SAT. 3-SAT's hardness then follows by reducing SAT into 3-SAT.

False. A valid verifier must accept some certificate exactly when the true answer is yes, and reject all certificates when the answer is no. Correctness, not just speed, defines NP.

False. Reductions preserve yes/no answers, not the quality of near-solutions. Approximability differs wildly — see Approximation Algorithms; Vertex Cover has a 2-approximation while general TSP has no constant-factor one unless P = NP.

Wrong. NP-completeness is about worst-case scaling, not individual instances. Many specific formulas (e.g. small ones, or those in special structured classes) solve instantly; hardness lives in the family, not every member.

Backwards conclusion. That reduction shows Clique is at least as hard as 3-SAT — it proves Clique is hard, not easy. A reduction transfers hardness forward along the arrow.

Error. Vertices for a literal and its negation must have no edge — picking both would set $x$ true and false simultaneously. Blocking that edge is what enforces a consistent assignment.

Error. TSP asks for a cycle (tour), which returns to start and uses exactly $n$ edges, so the correct budget is $B=n$. Using $n-1$ would reject every valid tour.

Error. A base like 10 (comfortably larger than the max per-column sum) is chosen so digit columns never carry into each other. Base 2 would let column sums overflow and corrupt neighbouring variable/clause bits.

Error. They are exact complements: $C=V\setminus I$. A vertex is in the cover or the independent set, never both — that partition is the whole duality.

Error. NP-hard means "at least as hard as everything in NP," which includes problems harder than NP — even undecidable ones like the Halting Problem. Only NP-hard problems that are also in NP are NP-complete.

Because $A{\le }_{p}B$ means "$B$ is at least as hard as $A$." To crown $B$ as hard we must show a known-hard $A$ hides inside it, so hardness flows into $B$.

A size-$m$ clique is forced to pick exactly one vertex per clause (no edges inside a clause), which corresponds to choosing one satisfying literal from every clause — precisely what satisfaction requires.

Verifying checks a single given certificate against the rules, while finding must search a possibly exponential space of candidate certificates for a valid one.

Any tour using even one weight-2 edge costs $\ge n+1>B=n$, so the budget already forbids fake edges; a finite penalty of 2 is enough and keeps the graph a clean complete weighted graph.

Cook–Levin encodes any NP machine's accepting computation as a Boolean formula, so SAT captures all of NP at once — making it the seed from which every other hardness proof grows via Polynomial-time Reductions.

A satisfied clause may contribute 1, 2, or 3 true literals, but the target fixes each clause column to 3. Slack values (1 and 2) let the subset top up any shortfall so the digit lands exactly on 3.

A single vertex, trivially "all pairwise adjacent" (there are no pairs to violate). Yes — any graph with $\ge 1$ vertex has a clique of size 1.

Yes — with no vertices there are trivially no internal edges. Its complement is all of $V$, the largest (and always valid) vertex cover.

Yes, if the empty subset is allowed: the empty sum is 0. This boundary case is why problem statements must state whether the empty subset counts.

Yes. A simple path graph $a\text{–}b\text{–}c$ has a Hamiltonian path but no cycle, since there's no edge closing $c$ back to $a$. The two problems are genuinely different.

The whole vertex set is one big independent set (and clique in $\bar{G}$), and the empty set is a valid vertex cover of size 0 — the duality $|C|=n-|I|$ still holds with $|I|=n$.

Not unless P = NP. A P-problem is in NP, but calling it NP-complete would mean every NP problem reduces to it, collapsing the whole hierarchy — the unresolved million-dollar claim.

On the reduced graph, no tour can cost less than $n$ (a cycle needs $n$ edges each costing $\ge 1$), so any budget $B<n$ is trivially unsatisfiable — the interesting threshold sits exactly at $B=n$.