Invariant First PvsNP Proposal

Abstract

This conceptual research note proposes an invariant-first, falsification-first research program for the P versus NP problem. It does not claim a proof of P=NP or P≠NP. Instead, it asks whether progress can be organized more effectively by shifting attention away from individual candidate algorithms and toward structural properties shared by entire classes of computation. The motivating asymmetry is simple. A negative result such as P≠NP cannot be established by defeating algorithms one at a time: there are infinitely many possible algorithms. A successful separation must therefore identify some property that every polynomial-time computation is forced to obey, and then show that exact solution of an NP-complete problem such as SAT cannot obey the same constraint. The proposal treats such properties as candidate class-level invariants and distinguishes two different targets. A separator invariant need only establish a one-way obstruction sufficient for a lower bound. A much stronger characterizing invariant would identify polynomial-time computation in both directions and could, in principle, support either resolution of the problem. This distinction prevents failure of a lower-bound invariant from being mistaken for evidence that P=NP. Version 2 strengthens the methodology by moving known proof barriers upstream into the design process. Candidate invariants are profiled early for interactions with relativization, Natural Proofs, algebrization, representation dependence, and related obstacles rather than being checked only after substantial effort has been invested. The program also introduces a standing easy-neighbor kill-set: before an invariant is allowed to explain the apparent hardness of SAT, it should survive comparison with structurally related tractable problems such as 2-SAT, Horn-SAT, XOR-SAT, bounded-treewidth dynamic programming, matching, and other relevant polynomial-time families. A central principle of the proposal is falsification before commitment. Candidate invariants are meant to be attacked aggressively. If an invariant fails universality, collapses under re-encoding, misclassifies an easy neighboring problem, or falls inside a known barrier regime without a credible escape route, it should be discarded rather than defended. The methodology is intentionally answer-neutral. It does not assume P=NP or P≠NP. Instead, it seeks a sequence of increasingly restrictive questions whose answers reduce the space of viable explanations and approaches. It is also proposed as a practical screening protocol for human- and AI-assisted complexity-theory claims, where strong-looking local successes can otherwise be mistaken for evidence about the full P versus NP problem. The guiding question is: What is the weakest structural property that every polynomial-time computation must possess, and does exact SAT decision necessarily violate it? The aim is not to provide the answer to P versus NP, but to propose a disciplined way of asking the question such that bad ideas can be killed early, surviving ideas become progressively sharper, and every intermediate result reduces uncertainty rather than merely defending a preferred approach.