Pith. sign in

reduction graph

P versus NP

Whether every language decidable in nondeterministic polynomial time is decidable in deterministic polynomial time.

5 statements · 4 links from papers · 0 composed · updated 2026-08-12 10:30:25.913044+00:00

Typed form: /api/frontier/p-vs-np · the inclusive shelf of every claim is at /topics/p-vs-np

Share X Bluesky LinkedIn Reddit HN

Derived, and unstated

Each of these follows from links two or more papers assert, but no paper in the corpus states it. A chain is only as strong as its weakest link, and the tier below reports that weakest link, not the best one.

  1. Nothing composes yet. That happens when the recorded links do not yet chain: a new paper reducing something to one of the classical criteria below is what starts it.

What would settle it

  1. This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually… implies the target

    paper/phrase · stated · arxiv:2005.00809

    This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually implies P ≠ NP as CLIQUE is NP-complete.

What it would settle

  1. the target implies among fractionally-polynomial maximization problems the new FFPTAS notion sits strictly between…

    paper · stated · arxiv:2603.17489

  2. the target implies an unconditional lower bound from the incomputability of KC, a biconditional characterization of P = NP via…

    paper · stated · arxiv:2606.31370

  3. the target implies for infinitely many k, unconditionally assuming P != NP).

    paper · stated · arxiv:2608.07800