Question bank — P vs NP — statement, why it matters

False. NP means Nondeterministic Polynomial = verifiable in poly time; since $P\subseteq NP$, even easy problems live inside NP, so NP is not a synonym for "slow."

True. Any poly-time solver doubles as a verifier that ignores the certificate and just solves the instance itself, so every P problem is automatically in NP.

False — it is open. Whether $NP\subseteq P$ is exactly the P vs NP question; most experts believe it's false but nobody has proved it.

False. NP-hard only means "at least as hard as all of NP"; it may lie outside NP — e.g. the Halting Problem (undecidability) is NP-hard yet undecidable, so it isn't even in NP.

False. Brute force being slow says nothing about the best algorithm; shortest-path and primality (AKS 2002) have naive slow approaches yet sit comfortably in P.

False (as far as we know). Verifying is clearly poly-time (check rows/cols/boxes); whether solving is also poly-time is precisely the open P-vs-NP mystery.

True. SAT is NP-complete (see Cook–Levin Theorem), so every NP problem reduces to it; a fast SAT solver would give fast solvers for all of NP.

True but trivially. You can try all $2^{|c|}$ possible certificates and verify each, giving an exponential deterministic solver — that's the ceiling, not evidence it can't be faster.

True. That is the plain-language soul of the statement: are yes-answers that are easy to verify always easy to discover?

False. They can be solved (they're decidable) — just not in polynomial time in the worst case; exact exponential algorithms and good heuristics still exist.

NP problems are all decidable; a machine can solve every one of them, just possibly slowly. "Never solvable" describes undecidable problems like the Halting Problem (undecidability), not NP.

Being in NP is not being NP-complete. Binary search is in P (hence in NP) but is nowhere near NP-hard; NP-complete needs every NP problem to reduce to it.

"Finite / solvable by trying everything" is not "polynomial." $n!$ grows faster than any $n^k$, so brute force does not place TSP-decision in P.

NP only requires a fast verifier of a given certificate, not a fast finder. You supply the witness and check it in poly time; finding it can be hard.

Factoring is perfectly decidable and even in NP (the factors are the certificate). RSA relies on factoring being believed hard to find, not impossible — and that safety evaporates if $P=NP$. See Cryptography and RSA.

No. Cook–Levin proved SAT is NP-complete (the first such problem); it says nothing about whether $P$ equals $NP$, which remains open.

It's the reverse: reducing A to B shows B is at least as hard as A, because a fast solver for B would solve A too.

Because solving is stronger than checking: a poly-time solver can be repackaged as a verifier $V(x,c)=A(x)$ that discards the certificate and just runs the solver.

Every NP problem reduces to each of them in poly time, so a single poly-time algorithm for one NP-complete problem would propagate through the reductions to solve them all → $P=NP$.

If the hint could be exponentially long, the verifier would need exponential time just to read it, destroying the whole point that verification is fast.

Brute force being exponential bounds only one algorithm from above; proving $P\ne NP$ requires showing no poly-time algorithm exists — a statement about all possible algorithms, which is far harder.

A valid verifier must accept some certificate on yes-instances and reject every certificate on no-instances; without the second condition a liar could always forge a hint and the definition would be useless.

$P=NP$ guarantees a polynomial algorithm exists in principle, but the constants and exponent could be huge; still, most security proofs assume hardness, so the theoretical guarantee collapses. See Cryptography and RSA.

Yes to both. Constant time is $O(n^0)$, a polynomial, so it's in P, and $P\subseteq NP$ places it in NP as well.

Yes. A verifier that rejects every input for every certificate is a valid poly-time checker with no yes-instances to satisfy, so it trivially lies in NP (and in P).

Yes. If it's NP-hard but sits outside NP (e.g. undecidable problems, or ones needing exponential certificates), it fails the "in NP" half and so isn't NP-complete.

No. "Known" refers to our current cleverness; a poly-time algorithm might exist undiscovered. Membership in P is about existence, not about what we've found so far.

It is NP-hard (all of NP reduces to it) but undecidable, hence not in NP — a clean example that NP-hard ⊄ NP.

No. With a constant bound on variables the search space is constant-sized, so it's decidable in $O(1)$ w.r.t. the rest of the input; NP-completeness of SAT needs the number of variables to grow with input size. See SAT and Boolean Satisfiability.