A colleague draws L inside P inside NP inside PSPACE inside EXPTIME and calls every step strict - which steps are actually proven?
answer
- containments known, strictness mostly not
- no adjacent step is settled
- proven separations skip levels
- endpoints differ, so something must
- hierarchy theorems supply the two
basics
~20 sNone of those four adjacent steps is proven strict; each one is open. The proven separations skip levels: the time hierarchy theorem puts P strictly inside EXPTIME, which forces at least one step in between to be strict.
solid answer
~40 sEvery containment in that chain is known, but none of the four adjacent steps - `L` versus `P`, `P` versus `NP`, `NP` versus `PSPACE`, `PSPACE` versus `EXPTIME` - has been proven strict; each is open. What is proven comes from the hierarchy theorems, and it skips levels: `P` is strictly inside `EXPTIME` by the time hierarchy theorem, and `L` is strictly inside `PSPACE` by the space hierarchy theorem. Those two facts are the useful part of the answer, because they force a conclusion: since the endpoints of the chain differ, the steps between them cannot all be equalities. At least one of `P` versus `NP`, `NP` versus `PSPACE`, `PSPACE` versus `EXPTIME` is a strict step - nobody can say which. Reading that off the picture is the difference between memorising it and understanding it.
go deeper
Recall the order of the chain and that each class is contained in the next. Knowing that containment is not the same claim as difference is already most of the value at this stage.
Explain why each containment holds - configuration counting for the two ends, reusing space to walk nondeterministic branches - and name which two separations the hierarchy theorems actually give you.
Show that you can reason with the picture rather than recite it: derive that at least one middle step must be strict, and correct a colleague who cites an open question as a settled result.
Own the distinction between a theorem and a well-supported conjecture in documents your organisation will act on, and make clear what a design loses if the conjecture it leans on ever fails.
## The chain, and why each containment holds Five classes, each defined by a resource budget on a machine that decides a language: - **L** - decidable with a read-only input and a work tape of size logarithmic in the input length. - **P** - decidable in time polynomial in the input length. - **NP** - decidable in polynomial time by a nondeterministic machine. - **PSPACE** - decidable using work space polynomial in the input length. - **EXPTIME** - decidable in time two raised to a polynomial. The containments themselves are not hard, and the reasons matter, because they are exactly what the hierarchy theorems cannot improve on: 1. **L inside P** - a machine with logarithmic work space has only polynomially many distinct configurations, so if it halts at all it halts within that many steps. 2. **P inside NP** - a deterministic machine is a nondeterministic one that never branches. 3. **NP inside PSPACE** - walk the nondeterministic branches one at a time, reusing the same work space for each. Space is reusable; time is not. 4. **PSPACE inside EXPTIME** - a machine using polynomial space `p(n)` has at most exponentially many configurations in `p(n)`, and a deterministic machine that halts never repeats a configuration, so it halts within that many steps. ## Which relationships are proven strict | Relationship | Status | Settled by | |---|---|---| | L inside P | **open** | no known technique | | P inside NP | **open** | the famous one | | NP inside PSPACE | **open** | no known technique | | PSPACE inside EXPTIME | **open** | no known technique | | P inside EXPTIME | **proven strict** | time hierarchy theorem | | L inside PSPACE | **proven strict** | space hierarchy theorem | | PSPACE inside EXPSPACE | **proven strict** | space hierarchy theorem | The pattern is the whole lesson. **Every proven separation here compares two budgets of the same kind that differ by more than a simulation overhead** - deterministic time against deterministic time, space against space, with an exponential gap between them. Every open step either changes the kind of resource (time to space) or the mode of the machine (deterministic to nondeterministic), and no known technique crosses either boundary. ## The consequence most people miss Because the endpoints of the chain are known to differ, the middle cannot be entirely flat: 1. P is strictly inside EXPTIME - that is a theorem. 2. P inside NP inside PSPACE inside EXPTIME is a chain of containments. 3. If all three of those steps were equalities, P would equal EXPTIME, contradicting step 1. So **at least one of the three is strict**, and nobody can say which. Running the same argument from the other proven separation, L strictly inside PSPACE, shows that at least one of L-to-P, P-to-NP, NP-to-PSPACE is strict. The open steps are not independently open: they are jointly constrained, and a candidate who sees that has understood the picture rather than memorised it. ## Why the adjacent steps resist - Separating **P from NP** would mean proving that no deterministic polynomial-time machine matches a nondeterministic one. The standard separation technique steps a machine like a black box, and that view is provably too weak here - an oracle result shows an argument of that shape cannot decide the question either way. - Separating **P from PSPACE** would mean proving that reusable memory is strictly more powerful than time inside polynomial budgets: the same mismatch of resource kinds. - Separating **L from P** would have to rule out every way of trading work space for repeated recomputation. - For restricted models of computation, strong lower bounds have been proven; they have not lifted to general machines, which is where the chain lives. ## Reading the picture in a design review - "X is inside Y" is a **containment**, not a claim of difference. Someone who says "P is inside PSPACE, so PSPACE is strictly bigger" has already made the error. - A claim that some separation is **proven** is checkable: ask which theorem. If the answer is not a hierarchy theorem, be suspicious. - The belief that P differs from NP is supported by decades of failed attempts, and that support is worth something - but it is not a proof, and a document should say which of the two it leans on. - A collapse is not absurd. P equalling PSPACE would contradict nothing proven; it would simply force PSPACE to sit strictly inside EXPTIME, which the theorems permit. ## What the chain does not tell you These are statements about **asymptotic worst-case** membership of whole problems, not about the instance in front of you. A problem living in a class with a large budget does not make your inputs hard, and a problem in P can carry a degree and constants that make it useless at your scale. The hierarchy answers what is provably impossible inside a budget; it never answers whether a given job finishes tonight.
- If someone proved P equals PSPACE tomorrow, would that contradict a proven separation?No. P sits inside PSPACE, which sits inside EXPTIME, and only P strictly inside EXPTIME is proven. P equalling PSPACE simply forces PSPACE to be strictly inside EXPTIME, which nothing rules out. The collapse would be astonishing, but it is consistent with every theorem we have.
- Which separations near this chain are proven, other than P strictly inside EXPTIME?L is strictly inside PSPACE and PSPACE is strictly inside EXPSPACE, both from the space hierarchy theorem. Every one of them compares the same kind of resource across an exponential gap in budget. No proven separation crosses from time to space or from deterministic to nondeterministic.
Think of nested boxes where you can see each one fits inside the next, but you may never open them to check whether two are secretly the same box. Weighing the outermost against the innermost proves they differ, so at least one nesting is real - without telling you which.
saying these in an interview costs you the question
- Says every arrow in the chain is a known strict inclusion
- Claims P differs from NP is proven because the field believes it
- Thinks nothing at all about the chain has been proven
- Asserts the hierarchy theorems already rule out P equalling PSPACE
- Believes the open steps could all turn out to be equalities