A Critique of a Polynomial-time SAT Solver Devised by Sergey Gubin

Simple item page
dc.creatorChristopher, Ian
dc.creatorHuo, Dennis
dc.creatorJacobs, Bryan
dc.date2008-04-16
dc.date.accessioned2026-07-07T09:33:08Z
dc.date.available2026-07-07T09:33:08Z
dc.descriptionThis paper refutes the validity of the polynomial-time algorithm for solving satisfiability proposed by Sergey Gubin. Gubin introduces the algorithm using 3-SAT and eventually expands it to accept a broad range of forms of the Boolean satisfiability problem. Because 3-SAT is NP-complete, the algorithm would have implied P = NP, had it been correct. Additionally, this paper refutes the correctness of his polynomial-time reduction of SAT to 2-SAT.
dc.identifierhttps://arxiv.org/abs/0804.2699
dc.identifierhttp://arxiv.org/abs/0804.2699
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/159027
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.titleA Critique of a Polynomial-time SAT Solver Devised by Sergey Gubin
dc.typetext

Files

Collections

arXiv