Which containment in the standard complexity hierarchy is *proven to be strict* (not merely conjectured)?
AP ⊊ NP — determinism is strictly weaker than nondeterminism in polynomial time
BNP ⊊ PSPACE — polynomial time is strictly weaker than polynomial space
CP ⊊ EXPTIME — polynomial time is strictly weaker than exponential time
DPSPACE ⊊ EXPTIME — polynomial space is strictly weaker than exponential time
P ⊊ EXPTIME is proven strictly by the time hierarchy theorem via diagonalization: given exponentially more time, you can solve problems no polynomial-time machine can solve. P ≠ NP is the most famous open problem in computer science — unresolved. NP ⊊ PSPACE and PSPACE ⊊ EXPTIME are also not proven as strict containments at the intermediate level. The key insight is that we know the hierarchy is strict *overall* (P ⊊ EXPTIME) but the intermediate separations remain open.
Question 2 Multiple Choice
A researcher proves P = NP. Which consequence follows for the polynomial hierarchy (PH)?
AOnly NP-complete problems become efficiently solvable; higher levels of PH are unaffected
BThe polynomial hierarchy collapses entirely to P — every level of PH becomes equivalent to P
CPSPACE collapses to P as well, since PSPACE ⊆ EXP and EXP would now equal P
DThe result affects NP and co-NP only, leaving Σ₂ and higher intact
If P = NP, then since Σ₁ = NP = P, and Σ₂ = NP^NP = P^P = P, and by induction every level of PH collapses to P. This structural consequence is one reason researchers expect P ≠ NP: the polynomial hierarchy appears to be genuinely infinite with strictly more power at each level, and a P = NP proof would wipe out this entire structure. This argument is suggestive, not a proof of P ≠ NP.
Question 3 True / False
It has been proven that P ≠ NP, establishing that nondeterminism provides a strict computational advantage over determinism in polynomial time.
TTrue
FFalse
Answer: False
P ≠ NP is one of the most famous open problems in mathematics and computer science — it has NOT been proven. It is widely believed to be true (most complexity theorists expect P ≠ NP), but no proof exists. What IS proven is that P ⊊ EXPTIME (strict), so the hierarchy is not entirely flat. Confusing 'widely believed' with 'proven' is a common misconception in this area.
Question 4 True / False
PSPACE contains NP as a subset: any problem solvable by a nondeterministic polynomial-time algorithm can also be solved using only polynomial space.
TTrue
FFalse
Answer: True
This containment NP ⊆ PSPACE is proven. A nondeterministic polynomial-time algorithm can be simulated in polynomial space: enumerate and verify each nondeterministic branch one at a time, reusing space between branches. Since space can be reused across time steps but time cannot be reused across space, polynomial space is at least as powerful as nondeterministic polynomial time. Whether PSPACE = NP is a separate (and open) question.
Question 5 Short Answer
The time hierarchy theorem proves P ⊊ EXPTIME using diagonalization. Explain why the same diagonalization argument does not directly prove P ≠ NP.
Think about your answer, then reveal below.
Model answer: The time hierarchy theorem works by constructing a machine D that runs in time T(n), simulates every polynomial-time machine, and deliberately differs from each one. For the P ⊊ EXPTIME proof, D has exponential time to simulate all polynomial-time machines — enough time to complete the simulation and flip the answer. The argument breaks for P vs. NP because NP uses nondeterminism. To diagonalize against all polynomial nondeterministic machines, D would need to simulate them deterministically — but that simulation requires potentially exponential time, blowing past D's polynomial budget. The argument 'runs out of time' before it can construct the separating language within P.
This is the technical barrier known as 'relativization' — naive diagonalization fails to separate P from NP because the simulation of NP machines does not fit in polynomial deterministic time. Proving P ≠ NP requires techniques that go beyond diagonalization, which is part of what makes it so difficult.