The P vs NP Problem is a cornerstone of theoretical computer science and asks whether every problem whose solution can be quickly verified can also be quickly solved.
Formally, it questions whether the complexity classes P (problems solvable in polynomial time) and NP (problems verifiable in polynomial time) are equal. A proof either way would have profound implications for cryptography, optimization, algorithms, and beyond.
This problem is deeply connected to what we can feasibly compute — and what remains forever beyond reach.
Honest status note:
What follows is a research hypothesis, not a proof, a model, or a completed construction. I'm
keeping it here — including the open questions — because MillenniumChecked exists to test the
relational-mathematics paradigm against real, hard problems, not to showcase only what already
works.
I construct a family of satisfiable 3-CNF formulas from a pseudorandom generator, each with a
unique planted solution and clauses dispersed widely across the variables. I then argue, via a
locality condition, that no small neighborhood of clauses is enough to recover any bit of the
solution — and from that, that no deterministic polynomial-time function can construct it, even
though a candidate solution is easy to verify.
Where things currently stand:
The locality argument (Lemma 2) rules out algorithms restricted to small neighborhoods of the
formula. It does not yet address polynomial-time algorithms that operate globally over the
whole instance — Gaussian-elimination-style methods, LP/SDP relaxations, message passing. Closing
that gap is the main open step before this becomes a full argument against all of FP.
The step from "hard to invert locally" to "behaves like a one-way function" currently treats
the generator's inversion-hardness as given rather than establishing it from first principles.
Uniqueness of the planted solution (Lemma 1) is stated as a high-probability property, not an
exact one; I'd like to tighten that to hold with certainty, or make the probabilistic version
precise.
In short: this page documents a direction I'm exploring, not a result I'm claiming.
📌 Status
Locality argument (Lemma 2): drafted
Case of general polynomial-time (non-local) algorithms: open
One-way generator property: currently assumed, not established
Solution uniqueness: probabilistic, not exact
Formal write-up: early draft (5 pp.), not peer-reviewed, no preprint