What would a constructive proof that P equals NP change about tasks whose answers are easy to check?
answer
- two halves of the same task
- recognising versus producing
- the cheap half swallows the expensive half
- only for short answers and fast checks
- bounded-length proofs become a search
basics
~20 sFinding would become as cheap as checking. Any object of modest size whose correctness a fast check can confirm — a schedule, a layout, a formal proof of bounded length, a key — could also be produced quickly, so the expensive half of the work disappears.
solid answer
~40 sThe stakes are not really about one problem getting faster; they are about a whole category of work changing shape. Today there is an enormous gap between recognising a good answer and producing one, and almost every hard engineering and mathematical task lives in that gap. A practical polynomial method for an NP-complete problem would close it: wherever a candidate answer of polynomial length can be checked in polynomial time, the answer itself could be found in polynomial time. Optimal schedules and layouts would replace heuristics, formal proofs up to a fixed length could be found mechanically, and design synthesis from a checkable specification would become routine. The caveats matter: the check must genuinely be polynomial, the answer must be short, and the proof must be constructive with usable constants.
go deeper
Hold on to the one-line version: checking a proposed answer and finding one are two different jobs today, and a collapse would make the second as cheap as the first.
Explain the shape rather than listing headlines. Name the conditions a task must meet — a short answer and a fast mechanical check — and give one example that meets them and one that does not.
Be able to separate a theoretical collapse from an operational one. Say what would have to be true of the algorithm's degree and constants before any system you run behaves differently.
The interesting judgment is which of your organisation's expensive problems are actually in this shape. Many are not, because their acceptance criteria are human, and no complexity result will change those.
## The gap the question is about Almost everything difficult has this shape: recognising a good answer is easy, producing one is hard. You can tell in minutes whether a delivery schedule respects every constraint; building the best one is a research problem. You can check a formal proof line by line; finding it is a career. You can verify that a key decrypts a message; recovering it is the attacker's whole job. This asymmetry between **checking** and **finding** is not a quirk of a few problems — it is the working assumption underneath optimisation, cryptography, mathematics and design. The open question asks whether the asymmetry is real. A constructive proof that the two classes coincide, with an algorithm you could actually run, would say it is not. ## What would change - **Combinatorial optimisation stops being heuristic.** Routing, packing, scheduling, placement and assignment problems are currently attacked with approximations and solvers that give no general guarantee. Optimal answers, not merely good ones, would be reachable for instances of realistic size. - **Mathematics changes character.** Whether a formal proof of at most N lines exists for a statement in a fixed formal system is exactly a search with a cheap check: verifying a formal proof is mechanical and fast. Fix the bound N and that search becomes polynomial. Finding proofs — the part everyone calls creativity — would become a matter of running a program with a big enough bound. - **Synthesis catches up with verification.** Today we can check that an artefact meets a specification far more easily than we can build one that does. Circuit designs, controller logic and programs judged against a bounded, mechanically checkable specification would be generated rather than written and then checked. - **Short explanations of data become findable.** Finding the shortest rule of bounded length that reproduces a dataset within a bounded number of steps is again a search whose check is cheap, so the modelling problem changes shape too. - **Everything resting on the gap between finding and checking loses its foundation.** Security built on the cost of inversion is the largest such structure, and it is treated in its own right. | Task today | Task after a practical collapse | |---|---| | Approximate a schedule, accept some slack | Produce the optimal schedule directly | | Verify a submitted proof | Search for a proof up to a chosen length | | Write code, then check it against a spec | Generate an artefact that satisfies the spec | | Guess a model, then score it | Find the shortest model that fits, given bounds | ## Where it would not bite The collapse only reaches tasks that genuinely have the shape it needs, and three conditions are easy to lose: 1. **The check itself must be polynomial.** 'Is this a good design?' answered by a week of human review is not a polynomial verifier. Wherever the acceptance test is subjective or expensive, nothing follows. 2. **The answer must be polynomially short.** A collapse says nothing about objects whose description is exponentially long — a full game strategy, an unbounded proof — because there is no short thing to hand back. 3. **The problem must be in NP in the first place.** Problems that are undecidable, or that live above NP such as the complete problems for polynomial space, are not reached. A collapse forces the polynomial hierarchy down to P but does not imply that polynomial space collapses too. ## Constructive versus non-constructive The question says *constructive* deliberately. A proof might establish that a polynomial algorithm exists without exhibiting one, and then nothing changes operationally on day one — though a known universal search procedure would then be guaranteed to run in polynomial time, with a multiplicative constant so vast that it would remain useless in practice. And a constructive proof that yields an algorithm of degree one hundred, or with a constant of astronomical size, changes the textbooks without changing any system. The gap between 'polynomial exists' and 'my scheduler now returns optimal answers' is wide enough that a careful answer names it. ## How to answer this in a room Lead with the shape of the change — search folding into verification — and then immediately qualify it with the three conditions above. The interviewer is checking whether you hold the slogan or the mechanism. 'Every hard problem becomes easy' is the slogan; 'anything with a short answer and a fast check becomes findable, provided the algorithm is real and its constants are usable' is the mechanism. The second answer also explains why the question matters to working engineers at all: it is the boundary between the problems we solve and the problems we approximate.
- Why is 'find a formal proof of at most N lines' a task with a cheap check?Because checking a formal proof is mechanical: each line must follow from earlier lines by a rule of the system, which a program confirms in time polynomial in the proof's length. Fixing the bound N makes the candidate polynomially short, so the whole thing has the checkable shape. Without the bound there is no short candidate and the argument does not apply.
- Would a collapse make optimisation problems with subjective goals solvable?No. The collapse only helps where acceptance is a fast mechanical test. If deciding whether a design is good requires human judgment, a market response or an expensive simulation, there is no polynomial verifier to piggyback on, and the search does not become cheap regardless of what happens to the classes.
saying these in an interview costs you the question
- Says every hard problem would become easy overnight
- Assumes the result would be constructive and the constants usable
- Applies the collapse to tasks whose answers are exponentially long
- Claims problems complete for polynomial space would also fall
- Ignores that the acceptance test must itself be fast and mechanical