pith. sign in

arxiv: 2005.00809 · v10 · pith:MS6EXITInew · submitted 2020-05-02 · 💻 cs.CC

On P Versus NP

Lev Gordeev This is my paper

Pith reviewed 2026-05-24 14:23 UTC · model grok-4.3

classification 💻 cs.CC
keywords P versus NPCLIQUE problemNP-completenessdeterministic Turing machinesmonotone algorithmspolynomial timecomputational complexity
0
0 comments X

The pith

The CLIQUE problem cannot be solved in polynomial time by any deterministic Turing machine.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the graph problem CLIQUE lies outside polynomial time for every deterministic Turing machine. It does so by extending an earlier result that applied only to monotone algorithms. Because CLIQUE is NP-complete, the claim directly yields P not equal to NP. A reader would follow the argument because it targets one of the longest-standing separations in complexity theory. The presentation also simplifies an earlier version while addressing prior technical objections.

Core claim

It is shown that graph-theoretic problem CLIQUE can't be solved in polynomial time by any deterministic TM. This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually implies P ≠ NP as CLIQUE is NP-complete.

What carries the argument

The lifting construction that carries the known monotone unsolvability of CLIQUE over to the full class of deterministic Turing machines.

If this is right

  • CLIQUE lies outside P.
  • P is not equal to NP.
  • No deterministic Turing machine decides CLIQUE in time bounded by any fixed polynomial.
  • The same separation holds for every NP-complete problem obtained from CLIQUE by polynomial reduction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same lifting technique, if sound, could be tested on other NP-complete problems whose monotone versions are already known to be hard.
  • Practical solvers that use non-monotone heuristics would still be forced into super-polynomial worst-case time on CLIQUE instances.
  • Any future deterministic poly-time algorithm for CLIQUE would have to violate one of the intermediate invariants used in the monotone-to-general step.

Load-bearing premise

The technical argument that lifts the known monotone unsolvability result to the general non-monotone case for deterministic Turing machines is free of errors and correctly models the full class of deterministic algorithms.

What would settle it

Either an explicit deterministic polynomial-time algorithm for CLIQUE on arbitrary graphs or a formal counter-example inside the lifting argument.

read the original abstract

It is shown that graph-theoretic problem CLIQUE can't be solved in polynomial time by any deterministic TM. This upgrades the well-known partial result that claims only monotone unsolvability thereof, and eventually implies P $\neq$ NP as CLIQUE is NP-complete. This paper essentially simplifies my previous presentation that used more complex models of computation based on standard Boolean semantics while fixing technical errors spotted by a generic proof assistant Isabelle that has been implemented by Ren\'e Thiemann.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims to show that the graph-theoretic problem CLIQUE cannot be solved in polynomial time by any deterministic Turing machine. This is presented as an upgrade to the known result of only monotone unsolvability, which would imply P ≠ NP because CLIQUE is NP-complete. The work simplifies prior models based on standard Boolean semantics and corrects technical errors previously identified by the Isabelle proof assistant.

Significance. If the central claim holds, the result would resolve the P vs NP question, one of the most significant open problems in theoretical computer science, with broad implications for complexity theory. However, the manuscript supplies no derivation, lemmas, or proof steps for the novel step of lifting the monotone unsolvability result to the general (non-monotone) deterministic TM case, so the significance cannot be assessed from the provided text.

major comments (2)
  1. Abstract: The central claim that CLIQUE cannot be solved in polynomial time by any deterministic TM is asserted without any derivation, lemmas, or proof steps. The author notes that prior versions contained technical errors caught by Isabelle, but the current text provides no independent verification that the simplified model correctly captures the full class of deterministic algorithms.
  2. Abstract: The upgrade from the known monotone unsolvability result to general deterministic TM unsolvability rests on an unshown argument that the simplified Boolean model excludes all non-monotone behaviors a general deterministic TM could exploit. Without this step, the implication to P ≠ NP does not follow.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their review and the opportunity to respond. We address each major comment below.

read point-by-point responses

  1. Referee: Abstract: The central claim that CLIQUE cannot be solved in polynomial time by any deterministic TM is asserted without any derivation, lemmas, or proof steps. The author notes that prior versions contained technical errors caught by Isabelle, but the current text provides no independent verification that the simplified model correctly captures the full class of deterministic algorithms.

    Authors: The abstract summarizes the claimed result. The manuscript describes a simplification of prior models while correcting errors identified by Isabelle. We agree, however, that the current text does not supply explicit derivation steps, lemmas, or verification that the model captures all deterministic algorithms. The revised manuscript will add a dedicated section containing these elements. revision: yes

  2. Referee: Abstract: The upgrade from the known monotone unsolvability result to general deterministic TM unsolvability rests on an unshown argument that the simplified Boolean model excludes all non-monotone behaviors a general deterministic TM could exploit. Without this step, the implication to P ≠ NP does not follow.

    Authors: The manuscript presents the simplified Boolean model as sufficient to lift the monotone result. We acknowledge that the explicit argument showing why non-monotone behaviors cannot be exploited is not provided with proof steps in the current text. The revised version will include a subsection detailing this lifting argument. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external NP-completeness and model simplification.

full rationale

The paper upgrades a known monotone unsolvability result for CLIQUE to the general deterministic TM case via a simplified Boolean model that fixes prior Isabelle-detected errors. This model simplification and the lift to non-monotone cases are presented as technical arguments independent of the target result. CLIQUE's NP-completeness is an external standard fact. No equations or definitions reduce the unsolvability claim to a self-fit, self-definition, or unverified self-citation chain; the central claim retains independent content from the modeling step. No load-bearing self-citation or ansatz smuggling is exhibited.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available; no free parameters, additional axioms, or invented entities are visible in the provided text beyond the standard assumption that CLIQUE is NP-complete.

axioms (1)
  • standard math CLIQUE is NP-complete
    Invoked in the abstract to conclude P ≠ NP from unsolvability of CLIQUE.

pith-pipeline@v0.9.0 · 5580 in / 1192 out tokens · 28893 ms · 2026-05-24T14:23:16.216123+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    A. E. Andreev, A method for obtaining lower bounds on the complexity of individual monotone functions , Dokl. Akad. Nauk SSSR 282:5, 1033–1037 (1985), Engl. transl. in Soviet Math. Doklady 31, 530–534

    work page 1985

  2. [2]

    R. B. Boppana, M. Sipser, The complexity of finite functions , in: Hand- book of Theoretical Computer Science A: Algorithms and Com- plexity, 758–804, MIT Press (1990)

    work page 1990

  3. [3]

    W. T. Gowers, Razborov’s method of approximations , gowers.files.wordpress.com/2009/05/razborov2.pdf

    work page 2009

  4. [4]

    C. H. Papadimitriou, Computational Complexity , Addison-Wesley (1995)

    work page 1995

  5. [5]

    A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, Dokl. Akad. Nauk SSSR 281:4, 798–801 (1985), Engl. transl. in Soviet Math. Doklady 31, 354–357 (1985)

    work page 1985

  6. [6]

    A. A. Razborov, Lower bounds on monotone complexity of the logical per- manent, Mat. Zametki 37:6, 887–900 (1985), Engl. transl. in Mat. Notes o f the Acad. of Sci. of the USSR 37, 485–493 (1985)

    work page 1985

  7. [7]

    A. A. Razborov, On the method of approximation , Proc. of the 21st Annual Symposium on Theory of Computing, 167–176 (1989)

    work page 1989

  8. [8]

    Sipser, Introduction to the Theory of Computation , PWS Pub- lishing (1997)

    M. Sipser, Introduction to the Theory of Computation , PWS Pub- lishing (1997)

    work page 1997

  9. [9]

    Tardos, The gap between monotone and non-monotone circuit complexi ty is exponential , Combinatorica 8:1, 141–142 (1988)

    ´E. Tardos, The gap between monotone and non-monotone circuit complexi ty is exponential , Combinatorica 8:1, 141–142 (1988)

    work page 1988

  10. [10]

    Erd˝ os, R Rado, Intersection theorems for systems of sets , Journal of London Math

    P. Erd˝ os, R Rado, Intersection theorems for systems of sets , Journal of London Math. Society 35, 85–90 (1960)

    work page 1960

  11. [11]

    Alweiss, S

    R. Alweiss, S. Lowett, K. Wu, J. Zhang, Improved bounds for the sunflower lemma, Proc. 52nd Annual ACM SIGACT Symp. on Theory of Computing, 624–630 (2020) https://doi.org/10.1145/3357713.3384234 16 4 Appendix A: Proof of Lemma 11 We use Lemma 3 and boolean inclusion A \B ⊆ (A \C) ∪ (C \B)

    work page doi:10.1145/3357713.3384234 2020

  12. [12]

    ∂ p (σ ∨ τ) = AC p (S (σ ) ∪ S (τ)) \ACp (AP (σ ) ⊔ AP (τ)) ⊆ ACp (S (σ ) ∪ S (τ)) \[ACp (AP (σ )) ∪ ACp (AP (τ))] ∪ [ACp (AP (σ )) ∪ ACp (AP (τ))] \ACp (AP (σ ) ⊔ AP (τ)) = [ACp (σ ) ∪ ACp (τ)] \[ACp (AP (σ )) ∪ ACp (AP (τ))] ∪ [ACp (AP (σ )) ∪ ACp (AP (τ))] \ACp (AP (σ ) ⊔ AP (τ)) ⊆ [ACp (σ ) \ACp (AP (σ ))] ∪ [ACp (τ) \ACp (AP (τ))] ∪ ∂ p ⊔ (AP (σ ), A...

    work page

  13. [13]

    ∂ p (σ ∧ τ) = AC p (S (σ ) ⊙ S (τ)) \ACp (AP (σ ) ⊓ AP (τ)) ⊆ ACp (S (σ ) ⊙ S (τ)) \[ACp (AP (σ )) ∩ ACp (AP (τ))] ∪ [ACp (AP (σ )) ∩ ACp (AP (τ))] \ACp (AP (σ ) ⊓ AP (τ)) = [ACp (σ ) ∩ ACp (τ)] \[ACp (AP (σ )) ∩ ACp (AP (τ))] ∪ [ACp (AP (σ )) ∩ ACp (AP (τ))] \ACp (AP (σ ) ⊓ AP (τ)) ⊆ [ACp (σ ) \ACp (AP (σ ))] ∪ [ACp (τ) \ACp (AP (τ))] ∪ ∂ p ⊓ (AP (σ ), A...

    work page

  14. [14]

    ∂ n (σ ∨ τ) = AC n (S (σ ) ∪ S (τ)) \ACn (AP (σ ) ⊔ AP (τ)) ⊆ ACn (S (σ ) ∪ S (τ)) \[ACn (AP (σ )) ∪ ACn (AP (τ))] ∪ [ACn (AP (σ )) ∪ ACn (AP (τ))] \ACn (AP (σ ) ⊔ AP (τ)) = [ACn (σ ) ∪ ACn (τ)] \[ACn (AP (σ )) ∪ ACn (AP (τ))] ∪ [ACn (AP (σ )) ∪ ACn (AP (τ))] \ACn (AP (σ ) ⊔ AP (τ)) ⊆ [ACn (σ ) \ACn (AP (σ ))] ∪ [ACn (τ) \ACn (AP (τ))] ∪ ∂ n ⊔ (AP (σ ), A...

    work page

  15. [15]

    ■ 17 5 Appendix B We have ℓ =m 1 8, p =ℓlog2m, L = (p − 1)ℓℓ!, k :=m 1 4, m ≫ 0

    ∂ n (σ ∧ τ) = AC n (S (σ ) ⊙ S (τ)) \ACn (AP (σ ) ⊓ AP (τ)) ⊆ ACn (S (σ ) ⊙ S (τ)) \[ACn (AP (σ )) ∩ ACn (AP (τ))] ∪ [ACn (AP (σ )) ∩ ACn (AP (τ))] \ACn (AP (σ ) ⊓ AP (τ)) ⊆ [ACn (σ ) ∩ ACn (τ)] \[ACn (AP (σ )) ∩ ACn (AP (τ))] ∪ [ACn (AP (σ )) ∩ ACn (AP (τ))] \ACn (AP (σ ) ⊓ AP (τ)) ⊆ [ACn (σ ) \ACn (AP (σ ))] ∪ [ACn (τ) \ACn (AP (τ))] ∪ ∂ n ⊓ (AP (σ ), A...

    work page

  16. [16]

    Then ⟨x,y ⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E

    Suppose x,y ∈ W . Then ⟨x,y ⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E

    work page

  17. [17]

    Then ⟨x1,y 1⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E

    Suppose x1,y 1 ∈ W1,x1 ∼ x ∈ W and y1 ∼ y ∈ W . Then ⟨x1,y 1⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E. 18

    work page

  18. [18]

    Then ⟨x,y 1⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E

    Suppose x ∈ W , y1 ∈ W1,y1 ∼ y ∈ W and ⟨x,y ⟩ ∈ ¬ E. Then ⟨x,y 1⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E

    work page

  19. [19]

    positive

    Suppose x1 ∈ W1,y ∈ W ,x1 ∼ x ∈ W and ⟨x,y ⟩ ∈ ¬ E. Then ⟨x1,y ⟩ ∈ E∗ ⇌ ⟨x,y ⟩ ∈ E. To complete the entire definition we assert r to be the root of B∗ , i.e. let V ∗ be the subset of V ∗ 0 whose vertices are reachable from r by chains of edges occurring in E∗ . Obviously |V ∗ | ≤ 2 |V |. It remains to verify the correctness of conversion֒→B∗ , i.e., that B...

    work page