A Counterexample to a Proposed Proof of P=NP by S. Gubin

2007/01/05 by Blake Hegerle, Hegerle, Blake
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.cs/0701033

2 pages

arxiv created 2007/01/05 · openalex publication_date 2007/01/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In a recent paper by S. Gubin [cs/0701023v1], a polynomial-time solution to the 3SAT problem was presented as proof that P=NP. The proposed algorithm cannot be made to work, which I shall demonstrate.

Related

• A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
• Does NP not equal P?
• A Critique of a Polynomial-time SAT Solver Devised by Sergey Gubin
• A Polynomial time Algorithm for 3SAT
• Does P = NP?