Question bank — NP — non-deterministic polynomial, verifier definition

True. If you can solve $L$ in polynomial time, you can verify it by ignoring the certificate and just re-solving — a solver is a lazy verifier, so $\text{P}\subseteq \text{NP}$.

False. NP means Nondeterministic Polynomial. It contains all of P, so plenty of NP problems are solved fast; the name is about guess-then-check, not about being unsolvable.

False in general. NP guarantees certificates only for yes instances. Short certificates for the no side define co-NP; whether NP $=$ co-NP is open.

False. The verifier itself must run in polynomial time. Both conditions — short certificate and fast check — are required together.

False. A polynomial-time verifier can't even read an exponential-length certificate, so the "check" is a fiction. The bound $|c|\le p(|x|)$ is essential.

True. Brute-force every certificate of length $\le p(|x|)$: there are at most $2^{p(|x|)}$ of them, each checkable in poly time, giving an exponential-time deterministic solver.

False. Nondeterminism accepts if some branch accepts (a logical OR over all branches). Randomness assigns probabilities and takes a majority/threshold — a different acceptance rule.

True. P $=$ NP would force every NP problem into P; a single NP problem outside P immediately separates them.

True. Boolean Satisfiability (SAT) is NP-complete (by Cook–Levin Theorem), so a poly-time SAT solver would put all of NP into P.

False. NP-complete problems are the hardest in NP (everything reduces to them). Easy problems like "is $x$ even?" are in NP but nowhere near complete.

You must also show the verifier checks that certificate in polynomial time. Short certificate alone isn't enough; a hard-to-check hint doesn't qualify.

You also need the converse: for every no-instance, no certificate makes $V$ accept. Otherwise $V$ could wrongly accept a no-instance, breaking the biconditional.

The complement of an NP language isn't automatically outside NP. PRIMES is actually in NP and even in P; complementation gives co-NP membership, not exclusion.

A solver is a verifier that ignores the certificate. Solving in poly time already puts you in P $\subseteq$ NP; no separate certificate is needed.

It must also verify every vertex appears exactly once (visiting all $n$ vertices). Checking edges alone would accept a short sub-loop that isn't Hamiltonian.

That's the definition of NP-hardness/completeness via Polynomial-Time Reductions, not NP membership. NP itself is defined by a poly-time verifier and short certificate.

A finite-but-huge (e.g. exponential) certificate couldn't be read in poly time, so every problem would trivially "qualify." The polynomial bound is what makes verification meaningful.

Because $x\in L⟺\exists c(V(x,c)=1)$ mirrors "there is a proof of yes." A no-instance has nothing to exhibit — the guarantee is that no certificate works. Demanding a certificate for "no" gives co-NP instead.

A nondeterministic machine guesses a string bit-by-bit, then checks it deterministically. That guessed string is exactly the certificate $c$, and the checking phase is exactly the verifier $V$ — the two views coincide.

EXP is a much bigger, looser bound; NP sitting inside EXP says nothing about whether it also fits inside the smaller class P. The gap between P and NP is untouched by the EXP upper bound.

Randomized acceptance uses probability thresholds, but NP's acceptance is a pure OR — accept iff some branch (certificate) works, even one out of exponentially many. That "some" is logical existence, not likelihood.

Yes. Take a verifier that always outputs $0$; then no certificate ever makes it accept, and there are no yes-instances to certify — the biconditional holds vacuously.

Yes. Use the empty certificate $c=\epsilon$ and a verifier that always accepts; it's actually in P, and P $\subseteq$ NP.

Yes, but $p(|x|)$ is then also tiny, so the certificate must be correspondingly short. The polynomial bound scales with the input; small inputs allow only small certificates.

Absolutely. SAT can have many satisfying assignments. NP only requires that at least one certificate exists for a yes-instance; multiplicity is fine.

Then it's an invalid verifier — the language it defines isn't $L$. A correct verifier must accept some certificate on every yes-instance and no certificate on any no-instance.

Trivially yes — a constant-time verifier answers it, and any constant-time solvable problem is in P $\subseteq$ NP. Degenerate inputs never break membership.

Yes — a poly-time solver doubles as a verifier that ignores the certificate.

Otherwise "easy to check" is meaningless; a slow checker would admit hard problems as trivially NP.

No — certificates exist only for yes-instances; the no-side guarantee is that no certificate accepts (that's co-NP's flip).