Questions: Nondeterministic Polynomial Time and NP

Question 1

A student argues: 'NP uses nondeterministic machines, so NP problems can be solved efficiently using randomized algorithms or massively parallel computers.' What is wrong with this claim?

• A. Randomized algorithms are strictly more powerful than nondeterministic machines, so they could solve NP problems but this hasn't been proven yet
• B. Nondeterminism in NTMs is a theoretical abstraction — it means an oracle-like ability to 'guess' the right path, not a model of randomization or parallelism that can be physically realized in polynomial time
• C. Parallel computers can solve NP problems in polynomial time, which is why P = NP is expected to be true
• D. The claim is essentially correct; randomized polynomial-time algorithms (BPP) are known to equal NP

Answer: (B)

Nondeterminism in the NTM model is an abstract computational power — the machine 'magically' branches into all possible computation paths simultaneously and accepts if any branch accepts. This is not the same as randomization (which picks one random path) or parallelism (which runs polynomially many paths in polynomial time). An NTM can explore exponentially many branches, all 'in parallel' in the theoretical model. No physically realizable computer is known to simulate this in polynomial time, which is precisely why P vs NP is open.

Question 2

Which of the following best captures why so many natural computational problems — scheduling, graph coloring, integer programming — fall into NP?

• A. These problems are all provably unsolvable in polynomial time, placing them naturally above P
• B. These problems all have exponential state spaces, requiring brute-force search
• C. These problems all have the structure 'does a solution exist satisfying these constraints?' — whenever a solution exists, it serves as a short, efficiently verifiable certificate
• D. These problems require nondeterministic hardware to solve efficiently

Answer: (C)

The verifier definition reveals NP's natural scope: problems asking 'does there exist an X satisfying condition Y?' When X exists, X itself is typically a short certificate (a schedule, a coloring, an assignment) that can be checked in polynomial time by an efficient verifier. The hard part is finding X; verifying X once found is easy. This 'easy to check, potentially hard to find' asymmetry is the hallmark of NP and explains its breadth across combinatorics, optimization, and constraint satisfaction.

Question 3

A language L is in P if and only if it is also in NP, since every deterministic polynomial-time algorithm can be viewed as a degenerate nondeterministic one.

• T. True
• F. False

Answer: True

P ⊆ NP: any deterministic polynomial-time algorithm is a nondeterministic machine that happens never to branch — it is trivially nondeterministic with only one computation path. Equivalently, if L is in P, a verifier for L can simply ignore the certificate and solve the problem directly in polynomial time. So every problem in P also satisfies the NP verifier definition. Whether NP ⊆ P — i.e., whether P = NP — is the open question.

Question 4

If a problem is in NP, it should be computationally hard — that is, it cannot be solved by any polynomial-time deterministic algorithm.

• T. True
• F. False

Answer: False

NP is not a class of 'hard' problems — it is a class of problems with efficient verifiers. Since P ⊆ NP, every problem solvable in polynomial time (e.g., sorting, shortest path, primality testing) is also in NP. The class NP includes both easy problems (those in P) and, under the widely believed conjecture P ≠ NP, hard ones. The hardest problems in NP are the NP-complete ones; membership in NP alone implies nothing about hardness.

Question 5

Explain what the certificate/verifier definition of NP reveals about why optimization and constraint-satisfaction problems fit so naturally into NP, using a specific example.

Model answer: The verifier definition captures a fundamental asymmetry: for these problems, a 'yes' answer comes with a witness — a short piece of evidence — that is easy to check even if it is hard to find. For graph 3-colorability, the certificate is a valid 3-coloring of the vertices: given the coloring, you can verify it in linear time by checking each edge. The hard part is determining whether any such coloring exists and finding it. This structure — existential quantification over a polynomially bounded witness, followed by polynomial-time verification — is exactly the template for optimization and constraint-satisfaction: 'does there exist an assignment, schedule, route, or configuration that satisfies these constraints?' The certificate is the solution itself, and the verifier checks feasibility.

NP captures the 'easy to verify, potentially hard to find' structure. Problems outside NP (like PSPACE-complete problems) cannot even be verified efficiently — they require checking all possible witnesses. NP problems are special precisely because candidate solutions are short and checkable, which is the computational signature of optimization over combinatorial objects.