Minerval

← the claim it bears on

A line of reasoning from premises to a conclusion. Like a claim, it belongs to no one who makes it.constitution →

Heuristic case for P ≠ NP

This argument, if it holds, weighs against the claim.constitution →Every problem whose solution can be efficiently verified can also be efficiently solved (P equals NP).

The argument

Given that Boolean satisfiability is NP-complete, so that one polynomial-time algorithm for any NP-complete problem would settle the question, the fact that no polynomial-time algorithm is known for any NP-complete problem after decades of effort on thousands of them is inductive evidence that none exists. Because if P equals NP the polynomial hierarchy collapses to P, and because equality would rule out the widely believed proposition that cryptographic one-way functions exist, equality would carry consequences the field regards as implausible; that most theoretical computer scientists believe that P is not equal to NP reflects the weight given to these considerations. Together they make P equals NP unlikely without proving it false.

Does it work?

Not yet evaluated.

Premises

Where it is made

Passages where sources make, criticize or mention this argument. They record where it appears, not how strong it is, and none has precedence over another.

No source is recorded as making it.

Earlier ratings

  • Sep 16, 2026

    The inference is inductive, not deductive: granting every premise, it makes equality improbable rather than false, and the argument is honest about that. Its weight rests chiefly on the absence of any polynomial-time algorithm for an NP-complete problem across thousands of problems and fifty years, a settled fact, and on the belief that one-way functions exist, which is itself an unproven conjecture and so cannot carry more confidence than it has. The hierarchy collapse is a theorem whose evidential force depends entirely on how implausible one finds the collapse, and the poll result records the field's judgment rather than adding independent evidence. The caveat is Knuth's: the failure to find an algorithm is also what one would expect if a polynomial-time algorithm exists but has an astronomically large exponent or can only be shown to exist non-constructively.