A researcher announces a proof that P = NP. Which of the following would be a direct consequence if the proof is correct?
APublic-key cryptographic systems such as RSA would no longer be provably secure, since integer factorization would be solvable in polynomial time
BBoolean satisfiability (SAT) would be proved to have no polynomial-time algorithm
CNP-complete problems would be reclassified as outside the NP complexity class
DThe Turing machine model would be invalidated as a foundation for complexity theory
If P = NP, every problem whose solution can be verified in polynomial time can also be solved in polynomial time. Integer factorization (which underlies RSA) is in NP — solutions can be verified easily — so it would have a polynomial-time algorithm, breaking RSA and most public-key cryptography. Option 1 reverses the consequence of P = NP versus P ≠ NP (SAT would gain a fast algorithm, not be proved to lack one).
Question 2 Multiple Choice
Which statement correctly captures the relationship between the complexity classes P and NP?
AP is the class of problems solvable in polynomial time; NP is the class where a proposed solution can be verified in polynomial time — every P problem is in NP, but NP may contain problems not in P
BP problems are computationally easy; NP problems are impossible to solve efficiently on any computer
CP and NP are the same class — this has been proved, which is why the Millennium Prize remains unclaimed
DP problems are solvable on deterministic machines; NP problems require quantum computers or nondeterministic hardware
NP stands for 'nondeterministic polynomial time' — the class of problems where a yes-certificate can be VERIFIED in polynomial time. P ⊆ NP always: if you can solve something quickly, you can verify it quickly. Whether NP ⊆ P (i.e., P = NP) is the open question. Options 2, 3, and 4 contain common misconceptions: NP does not mean 'impossible,' P = NP has NOT been proved, and NP is not about hardware type.
Question 3 True / False
Computer scientists have proved that P ≠ NP, establishing that verification is fundamentally easier than solving for certain problems.
TTrue
FFalse
Answer: False
P ≠ NP is the most famous open problem in computer science and remains UNPROVED. Most researchers believe P ≠ NP, and there is strong intuitive and empirical evidence for this belief, but no proof exists. It is one of the seven Millennium Prize Problems with a $1 million prize. This misconception — confusing widely-held belief with established fact — is one of the most important to correct.
Question 4 True / False
If P ≠ NP were proved, it would establish that NP-hard problems have no efficient algorithms in any practical context.
TTrue
FFalse
Answer: False
P ≠ NP establishes worst-case hardness — that no polynomial-time algorithm solves all instances of NP-hard problems. It says nothing about practical performance on typical instances. Heuristics, approximation algorithms, and special-case algorithms often work extremely well in practice even for NP-hard problems (e.g., modern SAT solvers handle millions of variables routinely). Worst-case hardness and practical difficulty are different things.
Question 5 Short Answer
Why is proving P ≠ NP considered extraordinarily difficult, even though most researchers believe it to be true and have believed so for decades?
Think about your answer, then reveal below.
Model answer: Proving P ≠ NP requires establishing a lower bound — showing that no possible algorithm, however cleverly designed, can solve certain problems in polynomial time. Lower bounds are notoriously hard to prove in complexity theory. Worse, barrier results (relativization, natural proofs, algebrization) show that most known proof techniques are fundamentally incapable of resolving the question — entire families of approaches have been ruled out. The problem requires mathematical machinery that doesn't yet exist.
The barrier results are particularly striking: they don't just say we haven't found a proof, they prove that certain systematic approaches CANNOT yield a proof. This rules out most of the toolkit that worked for other major results in complexity theory. The P vs. NP problem sits at the boundary of current mathematical understanding in a deep way.