skip to content

A plan leans on P and PSPACE being different, which is unproven - how should a lead weight a claim resting on a conjecture?

level: principalimportance: should knowfreq 36%

answer

  1. theorem, conjecture, observation - say which
  2. only exponential-gap separations are proven
  3. name the consequence if it fails
  4. asymptotic worst case, not your instance
  5. a collapse proof delivers no algorithm

basics

~20 s

Separate what is proven from what is believed, and record which one the plan rests on. P versus PSPACE is open, so depending on a separation there is a well-supported bet rather than a citation, and the document should name what breaks if the bet loses.

solid answer

~50 s

Treat it as a named assumption, not a theorem. Three grades of support get confused in design documents: a **theorem** (on this chain, only separations across an exponential gap qualify), a **conjecture** that the field overwhelmingly believes after decades of failure, and an **observation** that nobody has yet written a fast implementation. All three can justify a decision; only the first is a fact, and a reviewer is entitled to know which is being used. Then ask the question that actually matters for the plan: what would change if the assumption failed? Often the honest answer is "very little soon", because a collapse proof can be non-constructive or carry unusable constants - which makes the bet cheap and worth taking explicitly. Where the answer is "the whole design", the assumption deserves a mitigation, a monitoring signal, or a smaller blast radius.

go deeper

for a junior

Learn the habit rather than the theory: when a document says something is impossible, ask whether that is proven or believed. The answer changes what you may repeat to someone else.

for a middle

Be able to check the claim yourself - name which separations on this chain are theorems and which are open - so you can spot the substitution when it appears in a review.

for a senior

Write the assumption down with its failure consequence, and resist both errors: quoting an open question as a result, and discounting a genuine theorem as mere belief.

for a principal

Own the difference where it is expensive: in claims made outside the team, in architecture that wires one bet through everything, and in deciding that a fifty-year-old open question is a bet worth holding rather than a reason to wait.

## Three grades of support, and why the difference is operational | Support | Example on this chain | What it licenses | |---|---|---| | **Theorem** | Some problems decidable in exponential time provably lie outside P | An unconditional claim, forever | | **Conjecture** | P differs from PSPACE; P differs from NP | A bet with strong evidence, which must be labelled | | **Observation** | "Nobody has published a fast method for this" | A default, revisable by next month's paper | The distinction is not pedantry. A document that says "this is safe because P differs from PSPACE" invites a reader to stop thinking, because the sentence is shaped like a citation. A document that says "this assumes P differs from PSPACE, which is open and widely believed; if it fails, the following holds" invites the reader to check the consequence, which is the part anyone can actually act on. ## What the chain licenses unconditionally Very little, and it is worth knowing exactly how little: - **Proven:** P is strictly inside EXPTIME, and L is strictly inside PSPACE. Both come from hierarchy theorems and both span an exponential gap in budget. - **Open:** every adjacent step - L versus P, P versus NP, NP versus PSPACE, PSPACE versus EXPTIME. - **A derived fact worth quoting:** because P is strictly inside EXPTIME, the steps between them cannot all be equalities. At least one is strict, which is a genuine unconditional statement, even though it names no particular step. So a lead can write "some problems in exponential time provably need more than polynomial time" as a fact. Writing "problems in PSPACE provably need more than polynomial time" is writing a conjecture in the grammar of a theorem. ## What even a proven separation does not promise This is where leads misuse the material more often than they misquote it: - It is **asymptotic**. A separation is a statement about growth in the limit and says nothing about the input sizes a system actually handles. - It is **worst case over all instances**. Membership in a class is decided by the hardest inputs, not the inputs your users send. - It is about **whole problems**, not about the specific variant in the requirement. A tightened constraint changes the problem, and sometimes changes its class. - A **collapse would not deliver an algorithm**. An equality proof can be non-constructive or carry a degree and constants so large that nothing changes in practice. "If the conjecture falls, our design falls over tomorrow" is rarely true, and saying so honestly usually makes the bet cheaper than it first looks. ## Writing the dependency down 1. **Name the assumption** in one sentence, in the words the field uses, so a reader can look it up. 2. **Grade it**: theorem, conjecture, or observation. One word. 3. **State the consequence of failure** concretely - which component, which guarantee, on what timescale. 4. **State the detection signal**, if there is one. For a conjecture of this kind there usually is not, and saying so is more useful than implying there is. 5. **Decide the blast radius**: whether the bet is confined to one component or wired through the architecture. ## When the bet is fine, and when it is not - Leaning on a decades-old, heavily attacked conjecture for a **performance expectation** is ordinary engineering: the evidence is strong and the downside is slow, not sudden. - Leaning on it for a claim of **impossibility** stated to people outside the team - a customer, a regulator, a security review - deserves the qualifier, because the words there are read as guarantees and the reputational cost of an overstatement is real. - Refusing to plan until a separation is proven is not rigour, it is paralysis. These questions have been open for fifty years; "wait for the theorem" is not a schedule. - The failure to avoid in both directions: a team that cites an open question as settled, and a team that treats a proven hierarchy separation as if it were also merely believed. Knowing which is which is the whole skill being tested.

  • Which unconditional claim about this chain can a design document actually state?
    That some problems decidable in exponential time provably lie outside polynomial time, and that some problems in polynomial space provably lie outside logarithmic space - both from hierarchy theorems. Also that the steps between P and EXPTIME cannot all be equalities. Every adjacent step remains open.
  • If P were proven equal to PSPACE tomorrow, would the system's performance change overnight?
    Almost certainly not. An equality proof can be non-constructive, and even a constructive one may carry a polynomial degree and constants that beat nothing at realistic sizes. A theorem about classes is not a delivered implementation, which is why such a bet is usually cheap to hold explicitly.
  • A reviewer asks for evidence behind a conjecture the plan leans on. What is a legitimate answer?
    That the statement has been attacked for decades by many techniques, that known barriers explain why the standard approaches fail, and that no partial result points the other way. That is evidence about the state of knowledge, offered as evidence rather than dressed up as proof.

saying these in an interview costs you the question

  • Cites a believed separation in a document as if proven
  • Treats an open question as settled because the field expects an answer
  • Assumes a proven separation makes one concrete instance hard
  • Expects a collapse proof to yield a usable algorithm immediately
  • Refuses to plan at all until the separation is proven