Question bank — NP-hard — harder than NP, may not be in NP

False. NP-complete $=$ NP-hard AND in NP; NP-hard drops the membership requirement, so it is a strictly larger family that can even contain undecidable problems.

False. The Halting Problem is NP-hard yet undecidable; NP-hardness is only a lower bound on difficulty and places no ceiling.

False. Optimization TSP ("output the minimum tour length") is NP-hard but outputs a number, not a bit, so it isn't even the right type to be a language in NP.

False. That would make it NP-complete. NP-hardness only says everything in NP reduces into $L$; it says nothing about $L$ having a short certificate of its own.

True. NP-complete is defined as NP-hard plus membership in NP, so the "hard" half holds by definition — every complete problem is also hard.

False, and backwards. That shows $L$ is no harder than 3-SAT (essentially that $L$ is in NP). To prove hardness you need a known-hard problem reducing into $L$: $\text{3-SAT}{\le }_{p}L$.

False. Only the NP-hard problems that are also in NP (the NP-complete ones) would collapse into P. HALT stays undecidable regardless.

False. Being harder than NP-complete problems is exactly what an above-NP problem like HALT does, and it is still NP-hard because all of NP still reduces into it.

False. Cook–Levin goes the other way: it reduces every NP problem to SAT, so all of NP pours into SAT — that is what makes SAT hard.

True. By transitivity of ${\le }_p$, reducing one known-hard problem $K$ into your new $L$ ($K{\le }_{p}L$) inherits hardness from the whole class in a single step.

Direction is wrong. That places Vertex-Cover inside NP's difficulty; you must map 3-SAT into Vertex-Cover so the known-hard problem's difficulty transfers onto Vertex-Cover.

The proof needs a poly-time reduction (a translator), not a solver for HALT. We build a machine $M_{\varphi }$ that halts iff $\varphi$ is satisfiable — building the machine is fast even though running it forever might be needed.

Only the decision version ("tour of length $\le k$?") is NP-complete; the optimization version outputs a number and is not a language, so it can be NP-hard but never in NP. See Decision vs Optimization problems.

Wrong arrow again. $A{\le }_{p}L$ means $A$ (the hard one) is easier-or-equal, so it says $L$ is at least as hard — this is fine only if $A$ is the known-hard problem. If you instead had $L{\le }_{p}A$, you'd learn nothing about $L$'s hardness.

A certificate requires the problem to be a decision problem with a poly-time verifier. Undecidable NP-hard problems have no verifier at all — no future cleverness produces one.

No. The reduction itself must run in polynomial time; an exponential translator lets the translation, not $L$, hide the difficulty, so the argument collapses.

Transitivity of ${\le }_p$ holds for any three languages; NP-completeness of $B$ is irrelevant. Composing two poly-time reductions gives a poly-time reduction because a polynomial of a polynomial is a polynomial.

Because we want the problem's difficulty to dominate, not the translation's; polynomial-time glue is cheap enough that if $L$ were easy, the whole of NP would be easy too.

A fast solver for $L$ must yield a fast solver for the known-hard problem; that only works if the hard problem's instances translate into $L$'s instances, so the solver for $L$ can be reused.

The definition only imposes a lower bound ("everything in NP reduces to me"); it never caps the problem, so it may be undecidable or the wrong type (non-decision) and thus outside NP.

SAT has a short certificate (a satisfying assignment) checkable in poly time, so it's in NP; HALT has no decider whatsoever, so it fails NP membership while still absorbing all of NP's difficulty.

Because $A{\le }_{p}K{\le }_{p}L$ automatically gives $A{\le }_{p}L$, a single reduction from one known-hard $K$ into $L$ inherits the entire class NP without re-doing Cook–Levin.

NP is defined for languages with yes/no answers and checkable certificates; an answer that is a full number has no single-bit outcome to verify, so it is disqualified by type, not by difficulty.

$\text{P}=\text{NP}$ only collapses the class NP onto P; HALT is not in NP (it's undecidable), so nothing in that collapse can reach it. See P vs NP.

No under standard many-one reductions. A yes-instance of any $A$ must map to a yes-instance of $L$; with $\varnothing$ there are no yes-instances to hit, so satisfiable formulas have nowhere to go and the reduction breaks.

Only if $\text{P}=\text{NP}$. If some P problem were NP-hard, all of NP would reduce into it and be solvable in poly time, forcing $\text{P}=\text{NP}$ — currently unknown, so we assume no.

The class HALT as a whole is NP-hard and undecidable; restricting inputs changes the problem. Hardness is a property of the whole language, not of individual convenient instances.

No — it's exactly the interesting case. HALT is strictly harder (undecidable) than any NP-complete problem yet is still NP-hard, because "hard" is a floor, not a ceiling.

Yes. HALT and 3-SAT are both NP-hard, but 3-SAT (decidable) cannot in general reduce from HALT while staying poly-time-and-decidable-preserving — NP-hardness only guarantees NP reduces into each, not that they inter-reduce.

That $L$ is NP-complete — the two halves (hard + in NP) exactly compose into completeness.

No. The decision version is a different problem that happens to be in NP; the optimization version still outputs a number and remains outside NP by type.