What would a proof that P equals NP still fail to make computationally feasible?

## Why the limits are worth knowing The popular framing of the open question is a binary: either everything hard becomes easy, or nothing changes. Neither is right, and the interview value of this material is showing where the boundary actually sits. A collapse would change a great deal — search folding into verification is not a small consequence — but three separate walls stand regardless, and they fall into different categories. ## Wall one: undecidability is a different axis The classes in this discussion are all about **how much** of a resource a solvable problem needs. Undecidable questions are not expensive; they have no algorithm at any budget whatsoever. Asking whether an arbitrary program eventually stops is the standard example, and it is not a member of NP at all — there is no short certificate whose check settles it in general. A polynomial method for every NP problem therefore gives nothing here. The mistake to avoid is imagining a ladder with undecidable problems as the top rung of a resource scale; they are off the scale entirely. ## Wall two: the classes above NP A collapse of NP into P forces the whole polynomial hierarchy down to P — every level of alternating quantifiers above NP comes down with it. It does **not** follow that polynomial space collapses to P. Problems complete for polynomial space, such as deciding a fully quantified Boolean formula, are not put inside P by the assumption. And at least one separation is settled rather than conjectured: problems provably needing more than polynomial time stay outside P whatever happens to NP, which is the material of the inclusions and separations leaf. So even a total collapse leaves a hierarchy of genuinely harder problems above it. ## Wall three: polynomial is not a synonym for fast This is the wall engineers feel. A bound of the form constant times n to a power is polynomial by definition, no matter how ugly the constant and the power are. | Bound | Cost at n = 1000 | Practical? | |---|---|---| | n squared | about 10 to the 6 | Yes | | n to the 6, small constant | about 10 to the 18 | No, on any real machine | | 10 to the 12 times n to the 6 | about 10 to the 30 | Not in any physical sense | | n to the 100 | astronomically beyond that | Purely theoretical | An algorithm of the third kind is a legitimate polynomial-time algorithm and a legitimate proof of the collapse, and it would run no workload. Results like this already exist in other corners of algorithms — asymptotically superior methods whose constants keep them permanently on paper. ## Wall three and a half: the proof might name no algorithm A proof can establish that a polynomial algorithm exists without exhibiting one. In that case a known universal search procedure would be guaranteed to run in polynomial time, since it matches the best algorithm for the problem up to a constant factor plus verification cost — but that constant would be beyond astronomical. The assumption would be dead as a matter of mathematics while no attack existed as a matter of engineering, which is an uncomfortable and genuinely possible state. ## What is left over, and what still changes Beyond the walls sit the things that were never computational problems in the first place: - deciding which objective is the right one to optimise; - getting trustworthy data; - physical limits on measurement and communication. No complexity result speaks to these. It is worth closing the answer by not over-correcting. The three walls do not make the collapse unimportant. If the algorithm were constructive with usable constants, optimisation, synthesis, bounded proof search and every computational security assumption would change at once, which is about as large as an event in this field could be. The right register is precise rather than deflationary: name what would change, then name the three walls, then say which of them would matter to the system on the table.