P-versus-NP page
The P-versus-NP page
This page collects links around papers that try to settle the
"P versus NP" question (in either way).
Here are some links that explain/discuss this question:
of the "P versus NP" question by
Mathworld's
on "P versus NP"
The Wikipedia
on "P versus NP"
has a survey paper on
(Proceedings of the 24th Annual ACM Symposium on the Theory of
Computing, 1992, pp. 603-619).
has written a
on NP-completeness
Lance Fortnow and Steve Homer:
Scott Aaronson:
Avi Wigderson:
For a correct solution of the "P versus NP" question, the Clay
Mathematics Institute
will award a prize of $1.000.000.
More information on this prize is available at
Here is the outcome of an
on "P versus NP" conducted by
Here are the
why Oded Goldreich refuses to proof-read papers settling
the "P versus NP" question.
Here is what googlism thinks of
of a typical comp.theory newsgroup discussion of a typical
P=/!=NP proof.
Here is Homer Simpson on "P versus NP"
by Pavel Pudlak on "P versus NP"
Here is a (youtube)
on P and NP.
What Sir William Timothy Gowers
in his summer holidays 2013, and a
for his P versus NP notebook.
Scott Aaronson:
should you believe P not equal NP?
Milestones
The following paragraphs list many papers that try to contribute to
the P-versus-NP question.
Among all these papers, there is only a single paper that has
appeared in a peer-reviewed journal, that has thoroughly been verified
by the experts in the area, and whose correctness is accepted by the
general research community: The paper by Mihalis Yannakakis.
(And this paper does not settle the P-versus-NP question, but "just"
shows that a certain approach to settling this question will never work
In 1986/87 Ted Swart (University of Guelph) wrote a number of papers
(some of them had the title: "P=NP") that gave linear programming
formulations of polynomial size for the Hamiltonian cycle problem.
Since linear programming is polynomially solvable and Hamiltonian cycle
is NP-hard, Swart deduced that P=NP.
In 1988, Mihalis Yannakakis closed the discussion with his paper
"Expressing combinatorial optimization problems by linear programs"
(Proceedings of STOC 1988, pp. 223-228).
Yannakakis proved that expressing the traveling salesman problem by a
symmetric linear program (as in Swart's approach) requires exponential
of this paper has been published in
Journal of Computer and System Sciences 43, 1991, pp. 441-466.
(Volume 1, 1996, pp. 16-29) of the
"SouthWest Journal of Pure and Applied Mathematics"
contains the
"Polynomial-Time Partition of a Graph into Cliques"
by the Ukrainian mathematician
This article designs a polynomial time algorithm for an NP-hard
graph problem, and thus proves P=NP.
(SWJPAM is an electronic journal devoted to all aspects of
Pure and Applied mathematics, and related topics.
Authoritative expository and survey articles on subjects of
special interest are also welcomed.
SWJPAM serves as an international forum for the publication of
high-quality strictly peer-reviewed original research articles.
The article is usually sent to at least two experts in the area.
Two positive reviews are required for the acceptance and
publication of any submitted article.)
Around 1997 Tang Pushan provided a polynomial algorithm for the clique problem.
The two relevant papers are
"An algorithm with polynomial time complexity for finding clique in a graph"
by Tang Pushan (Proceedings of 5th International Conference on CAD&CG, Shenzhen,
P.R. China, 1997, pp 500-505) and
"HEWN: A polynomial algorithm for CLIQUE problem"
by Tang Pushan and Huang Zhijun (Journal of Computer Science & Technology 13(Supplement),
1998, pp 33-44).
Clearly this implies P=NP.
Zhu Daming, Luan Junfeng and M. A. Shaohan (all affiliated with Shandong University, China)
refute these claims in their paper
(Journal of Computer Science and Technology 16, 2001, pp 388-391).
Here is Miron Telpiz's
on his proof of P=NP.
His main theorem reads:
"The class of NP-complete problems is coincides with the class P".
The proof of this theorem has been derived in the second half of the
year 2000, and it is contained in the book
"Positionality principle for notation and calculation the functions
(Volume One)".
[Not equal]:
The 3rd International Conference on Information and Communications
Security (ICICS 2001) took place in Xian, China, November 13-16, 2001.
of ICICS 2001 have been published as Volume 2229 of Springer Lecture Notes
in Computer Science.
Pages 495-501 of these proceedings contain the
"Redundancy, Obscurity, Self-Containment & Independence" by Seenil G
this paper first proves the so-called "Indistinguishability Lemma" and
then deduces (on the top of page 501) as a simple, direct corollary
that EXP is contained in NP.
Seenil Gram has also provided some additional
on his breakthrough result in the newsgroup "sci.crypt".
(Thanks to Daniel Marx for providing this link.)
In May 2002 Charles Sauerbier designed a polynomial time algorithm for
the satisfiability problem.
This algorithm employs an unconventional approach premised on set theory
(which does not use search or resolution) to partition the set of all
assignments into nonsatisfying and satisfying assignments.
"A polynomial time (heuristic) SAT algorithm"
can be found at the "arXiv.org e-Print archive".
In September 2003, a hole has been found in the algorithm:
An eleventh hour change admits a path inconsistency.
The inconsistency arises due to an improper closure of a path to a cycle
against a root not supportive of the path. The mathematical basis of the
algorithm remains supportive of the intended solution, and a revision
of the algorithm is underway.
Here is a link to a
by Givi Bolotashvili that proves P=NP.
The title of the paper is
"Solution of the Linear Ordering Problem (NP=P)".
The paper has been archived in March 2003 at the
"arXiv.org e-Print archive".
An earlier version of this paper appeared in 1990 in the
journal "Soobshcheniya Akademii Nauk Gruzinskoi SSR" under the title
"A polynomial algorithm for a problem of linear orders".
This version was written in Russian with an English and a Georgian
[Undecidable]:
Nicholas Argall proved on 25 March 2003 that P=NP is undecidable.
His main line of argument is that a provable answer to the P=NP question
requires a complete and consistent formal statement of the question.
Then he invokes Goedel's theorem and deduces that P=NP is undecidable.
The proof is actually quite short:
(Thanks to Daniel Marx for pointing me to this result.)
[Unprovable]:
The journal "Applied Mathematics and Computation"
addresses work at the interface between applied mathematics,
numerical computation, and applications of systems-oriented ideas to
the physical, biological, social, and behavioral sciences, and emphasizes
papers of a computational nature focusing on new algorithms, their
analysis and numerical results.
Applied Mathematics and Computation 145 (2003), pp. 655-665,
contains the
"Consequences of an exotic definition for P=NP"
by N.C.A. da Costa and F.A. Doria.
This article shows that "P-not-equal-to-NP" is unprovable in ZFC.
of this proof by the German logician
Andreas Blass, the reviewer of this paper in the AMS Mathematical
Reviews, writes in his review MR04f:03076):
"The authors claim to prove (Corollary 4.6) that, if ZFC is consistent,
then it remains so when P=NP is added as an additional axiom.
Unfortunately, there is an error in the proof [...]."
[Not equal]:
with a really short argument that "P-not-equal-to-NP":
"Proof by contradiction. Assume P=NP.
Let y be a proof that P=NP. The proof y can be verified
in polynomial time by a competent computer scientist, the
existence of which we assert. However, since P=NP, the
proof y can be generated in polynomial time by such computer
scientists. Since this generation has not yet occurred
(despite attempts by such computer scientists to produce
a proof), we have a contradiction."
Here is a link to the
"Evidence that P is not equal to NP"
by Craig Alan Feinstein.
This paper does not claim to settle the "P versus NP" question,
but provides some evidence for "P-not-equal-to-NP" in a certain restricted
model of computation.
An earlier
"P is not equal to NP"
by the same author has been withdrawn, since a counter-example had been found.
Both papers have been archived in 2003/04 at the "arXiv.org e-Print archive".
[Not equal]:
In 2004, Ki-Bong Nam, S.H. Wang, and Yang Gon Kim published the paper
"Linear Algebra, Lie Algebra and their applications to P versus NP"
Journal of Applied Algebra and Discrete Structures, on pages 1-26
of volume 2.
This journal is published by SAS Int. Publ., Delhi, India.
The paper defines a counting problem which purports to be a counterexample
Richard K. Molnar, the reviewer of this paper in the AMS Mathematical
Reviews, writes in his review MR05e:68070):
"The crux is the assertion that the problem is not solvable in polynomial
time because the relevant system of equations contains expressions not just
determined from the data but also random variables.
The calculations are lengthy, complex, and difficult to follow, and the
assertion of non-computability in polynomial time is not convincing to the
reviewer."
(Thanks to Hwasop Lihm for guiding me to these informations.)
[Not equal]:
In spring 2004 Mikhail N. Kupchik started a series of papers that aim
at proving "P-not-equal-to-NP".
At that time, Mikhail Kupchik was a 3rd year undergraduate of the department
of applied mathematics at the University of KPI, Kiev, Ukraine.
The papers in that series are all called
"P versus NP problem solution".
They are available as
Here is another
with the title "P=NP".
It has been archived in June 2004, and it proves that P=NP.
The authors are Selmer Bringsjord and Joshua Taylor.
They look forward to receiving the $1 million Clay prize but concede
that they provide a meta-level argument.
(Thanks to Tuerker Biyikoglu for providing this link.)
[Not equal]:
In the essay "Some consequences of defining mathematical objects
constructively and mathematical truth effectively" from 2004,
Bhupinder Singh Anand considers a constructive interpretation of
classical first order theory in which he argues that the class P of
polynomial-time languages in the P-versus-NP problem may define a
mathematical concept that cannot be added as a formal mathematical
symbol to the theory without inviting contradiction.
In the paper "A density-based approach for non-heuristic approximations
of prime counting functions" from 2015,
Bhupinder Singh Anand shows that the prime divisors of any integer n are
mutually independent, and concludes that any deterministic algorithm
which always computes a prime factor of n is necessarily of the order
O(n/log n). Hence Integer Factorising cannot be polynomial-time,
whence P is not equal to NP.
The paper is available at
[Not equal]:
Marius Ionescu has written a
with the title "P is not NP".
The paper has been archived in September 2004.
It introduces the OWMF (One Way Mod Function) problem.
It shows that OWMF is in NP, but cannot be solved in polynomial
time, since there is no faster algorithm other then exhaustive
search for it.
Marius Ionescu also maintains a web-page
where he applies his results on the "P versus NP" question
to cryptographic systems.
In particular, Ionescu uses his insights into the 1WayFx Model to
construct the MI cryptosystem, a unique new security solution,
without the need of SSL, PKI, or third party involvement.
The MI cryptosystem solves today's major implementation issues,
including difficulty of deployment, data/message integrity, security
exposure, and performance.
(Thanks to Jeff Erickson and Maxim Sviridenko for providing these links.)
In October 2004, Moustapha Diaby constructed a linear programming
formulation for the travelling salesman problem (TSP).
His paper is called "P=NP: Linear Programming Formulation of the
Traveling Salesman Problem", and it is available at
The correctness of Diaby's proof is frequently discussed in the
newsgroup comp.theory.
In reaction to these discussions in comp.theory, the paper has
been revised and clarified many times.
A new version of the paper can be found at
(uploaded: 2 Sep 2006).
In October 2005, Moustapha Diaby also constructed a linear programming
formulation of the QAP (quadratic assignment problem).
This yields yet another proof that P=NP.
The paper is available at
A new version of the paper can be found at
(uploaded: 2 Sep 2006).
version of the QAP paper has been published in the 2006 IMECS Conference Proceedings (ISBN: 988-).
This version was also awarded a "Certficate of Merit Award" by the conference organizers (IAENG).
In 2010, Moustapha Diaby provided two further proofs for P=NP.
His papers
give linear programming formulations for two well-known NP-hard problems.
Both papers were published in the "International Journal of Operational Research (IJOR)".
In April 2016, Moustapha Diaby and Mark H Karwan published the book "Advances in Combinatorial Optimization "
with World Scientific Publishers.
The book is available at the website
The book presents a generalized framework for formulating hard combinatorial optimization problems
as polynomial sized linear programs, and hence implies P=NP.
(Thanks to Andrea Lodi, Philipp Lucas, Silvano Martello, Patric &Osterg&rd,
Philippe Schnoebelen, and Ugo Vaccaro for providing some of these links.)
[Not equal]:
In November 2004, Mircea Alexandru Popescu Moscu introduced an
invariance principle of complexity hierarchies.
His paper is available at
and seems to prove that P is not equal to NP, if "you are willing
to believe that the property of a complexity class to be closed
or openend to the nondeterministic extension operator it's an
invariant of complexity theory".
In January 2005, Andrea Bianchini proved that P is equal to NP, by constructing a polynomial time
exact algorithm for the NP-hard SubsetSum problem.
His paper "A Polynomial-time Exact Algorithm for the Subset Sum Problem"
is available as .
(Thanks to Philip Bille for providing some pointers.)
[Not equal]:
In February 2005, Raju Renjit Grover proved that P is not equal to NP,
and also that P is not equal to co-NP.
His paper is available at
The paper proves that (i) all algorithms for the NP-hard clique problem are of a
particular type, and (ii) that all algorithms of this particular type are not
polynomial in the worst case.
(Thanks to Daniel Marx for providing this link.)
[Not equal]:
In March 2005, Dr. Viktor V. Ivanov proved that P is not equal to NP.
His proof is based on better estimates of lower bounds on time
complexity that hold for all solution algorithms.
Almost no special knowledge other than logical and combinatorial
efforts is needed to understand the proof.
Here is the
for this paper.
In 2014, a new version of the proof has been published in the
International Journal of Pure and Applied Mathematics
The paper is available at the following
(Thanks to Boaz Barak for providing this link.)
[Not equal]:
In June 2005, Bhupinder Singh Anand proved that P is not equal to NP,
under the assumption that every Turing-decidable true
arithmetical relation is provable in Peano Arithmetic.
His paper is called "Is the Halting problem effectively solvable
non-algorithmically, and is the Goedel sentence in NP, but not in P?",
and it is available as
The paper shows that (under a provability assumption as above)
Goedel's arithmetical predicate R(x), treated as a Boolean function,
is in the complexity class NP, but not in P.
(Another interesting result in this paper states that the Halting
problem is effectively solvable, albeit not algorithmically.)
(Thanks to Ugo Vaccaro for providing this link.)
[Not equal]:
In July 2005, Craig Alan Feinstein wrote the paper
This paper explains why P is not equal to NP in the so-called Mabel-Mildred-Feinstein
model of computation.
The paper also kind of settles the Collatz 3n+1 Conjecture:
Every valid proof in the Feinstein-model-of-proof must have an infinite number of lines.
A similar statement is shown to hold for the Riemann Hypothesis.
Another version of this paper appeared under the titel
in Progress in Physics, July 2006.
claims to be a quarterly, peer-reviewed scientific journal of advanced studies in
theoretical and experimental physics, including related themes from mathematics.
(Thanks to Clyde P. Kruskal for providing some of these links.)
[Not equal]:
In Summer 2005, Lev Gordeev showed a way how to prove that P is not equal to NP.
His proof is not yet complete, but he states that what remains to be done is
technical work along the lines of traditional combinatorics.
Several relevant papers are available from a
at the University of Tuebingen (Germany),
and in particular
(Thanks to Omar Al-Khayyam and Sebastian Schoener for providing these links.)
In October 2005, Lokman Kolukisa designed a polynomial time algorithm for
recognizing tautologies.
This implies P=co-NP, and hence also P=NP.
His paper is called "Two Dimensional Formulas and Tautology Checking"
and it is available
(Thanks to Moritz Hammer for providing this link.)
In November 2005, Francesco Capasso constructed a polynomial-time algorithm
for Circuit-SAT.
This implies P=NP.
The paper is available at
Versions 1, 2, and 3 of this paper (that have been uploaded to
the archive, respectively, on Nov 18, 22, and 23) were called
"A polynomial-time algorithm for Circuit-SAT".
From Version 4 (uploaded Nov 28) onwards, the paper is called
"A polynomial-time heuristic for Circuit-SAT".
(Thanks to Luca Trevisan for providing this link.)
[Not equal]:
In November 2005, Ron Cohen proved that P is not equal to NP.
In addition, his paper shows that P is not equal to the
intersection of NP and co-NP.
Finally, the exact inclusion relationships between the classes
P, NP and co-NP are discussed.
The paper is available at
The title of the paper is
"Proving that P is not equal to NP and that P is not equal to the intersection of NP and co-NP".
(Thanks to Vahan Mkrtchyan for providing this link.)
In December 2005, Miron Teplitz proved P=NP.
His paper "Sigma-notation and the equivalence of P and NP classes"
was published in Journal of Information and Organizational Sciences (JIOS),
Faculty of Organization and Informatics, Croatia.
The paper is available at the page
In 2005, Dr. Joachim Mertz proved P=NP.
His main contribution is a linear programming formulation of the
TSP with O(n^5) variables and O(n^4) constraints.
More information about this approach can be found at
[Not equal]:
In March 2006, Bhupinder Singh Anand proved that P is not equal to NP:
The title of the paper is
"P =/= NP".
The paper shows that all provable arithmetical formulas are Turing-decidable under the
standard interpretation of a standard, first-order, Peano Arithmetic, PA.
An immediate consequence is that the set of Goedel-formulas of PA is empty, and that
PA has no non-standard models. This implies P=/=NP.
[Not equal]:
In July 2006, Craig Alan Feinstein provided yet another version of his
proof that P is not equal to NP.
The paper is available at
The title of the paper is
"A New and Elegant Argument that P is not NP"
A response to this proof appeared in June 2007 in the article
by Kyle Sabo, Ryan Schmitt, and Michael Silverman.
The final version of this paper appeared under the titel
in Progress in Physics, 2011, Volume 2, on pages 30-31.
(Thanks to Luca Trevisan, Clyde P. Kruskal and Neil McKay for providing these links.)
In August 2006, Mohamed Mimouni proved P=NP by constructing a polynomial
time algorithm for the clique problem.
His paper (in French) is available at
Here are some
by Radoslaw Hofman on this proof.
In October 2006, Sergey Gubin proved P=NP by constructing a polynomial
time algorithm for the directed Hamiltonian cycle problem.
His paper is available at
The title of the paper is
"A Polynomial Time Algorithm for The Traveling Salesman Problem".
Here are some
by Radoslaw Hofman on this proof.
And here is a full
of Gubin's arguments by Ian Christopher, Dennis Huo, Bryan Jacobs from April 2008.
(Thanks to Juergen Ernst for providing the link to Christopher, Huo, and Jacobs.)
[Not equal]:
In 2006, Radoslaw Hofman proved that P is not equal to NP (under the
assumption that deterministic Turing machines only use deterministic
calculation models).
His paper "Complexity Considerations, cSAT Lower Bound"
is available at
In November 2006, Raju Renjit proved that co-NP is equal to NP:
The title of the paper is
"co-NP Is Equal To NP".
By investigating the clique problem, the author recognizes that there exists a
case where the time complexity of NP and co-NP are the same in the worst case.
This result nicely complements an earlier paper by Renjit (from February 2005),
where he proves that P is not equal to NP.
[Not equal]:
In November 2006, Rubens Ramos Viana proved that P is not equal to NP:
The title of the paper is
"Using Disentangled States and Algorithmic Information Theory to Solve the P Versus NP Problem".
Viana uses (i) the Chaitin number Omega and (ii) the fact that the general
decomposition of an N-way disentangled state is an irreducible sentence
whose number of coefficients grows in a non-polynomial way with N,
to construct an NP problem that can never be solved in P.
In December 2006, Howard Kleiman proved that P is equal to NP:
The title of the paper is
"The Asymmetric Traveling Salesman Problem".
Kleiman uses a modification of the Floyd-Warshall algorithm to solve
the Asymmetric Traveling Salesman Problem in polynomial time.
In 2006, Khadija Riaz and Malik Sikander Hayat Khiyal proved that P is equal to NP:
The title of their paper is
"Finding Hamiltonian cycle in polynomial time".
The result has been published in the Information Technology Journal 5 (2006), pages 851-859.
(Thanks to Joe Mitchell for providing this link.)
In June 2007, Anatoly D. Plotnikov established P=NP by developping an experimental algorithm
for the exact solving of the maximum independent set problem.
The theoretical estimation of the running time on n-vertex graphs is O(n^8).
The algorithm was tested by a program on random graphs, and the testing confirmed the correctness
of the algorithm.
The paper "Experimental Algorithm for the Maximum Independent Set Problem" is
available at
(Thanks to Mathieu Chapelle for providing this link.)
In summer 2007, Guohun Zhu proved that P is equal to NP:
The title of the paper is
"The Complexity of HCP in Digraps with Degree Bound Two".
Zhu uses techniques from matching theory to design a polynomial time
solution for the NP-hard Hamiltonian Cycle problem in bipartite cubic graphs.
contains an outline of the argument.
(a) In August 2007, Matthew Delacorte proved that he graph isomorphism problem
is PSPACE-complete:
His (very short) paper is titled
"Graph Isomorphism is PSPACE-complete".
This result does not settle the P-versus-NP question, but it does imply NP=PSPACE.
(b) In November 2007, Reiner Czerwinski proved that the graph isomorphism problem
is polynomially solvable:
The paper is titled
"A Polynomial Time Algorithm for Graph Isomorphism";
it proposes an algorithm that has polynomial complexity, and constructively
supplies the evidence that graph isomorphism lies in P.
In combination, the two results in (a) and (b) imply that P=PSPACE, which of
course yields P=NP as a corollary.
(Thanks to Marcus Ritt for providing the link to Delacorte, and
thanks to Jan van Leeuwen for providing the link to Czerwinski.)
In March 2008, Cynthia Ann Harlan Krieger applied for a patent for a polynomial time solution for
the (NP-complete) Hamiltonian circuit problem:
The full proofs of the underlying theorems are available in the paper
by Cynthia Ann Harlan Krieger and Lee K. Jones.
(Thanks to Alasdair Urquhart for providing these links.)
[Not equal]:
In April 2008, Jerrald Meek proved that P is not equal to NP:
The title of the paper is "P is a proper subset of NP".
The paper demonstrates that as the number of clauses in a NP-complete problem
approaches infinity, the number of input sets processed per computations performed
also approaches infinity when solved by a polynomial time solution.
It is then possible to determine that the only deterministic optimization of an
NP-complete problem that could prove P=NP would be one that examines no more than
a polynomial number of input sets for a given problem.
By demonstrating that at least one NP-complete problem exists that can not be solved
by checking a polynomial subset of the total set of possible input sets, it then
follows that P is not equal to NP.
[Not equal]:
In June 2008, Bhupinder Singh Anand proved that P is not equal to NP
In this paper "A trivial solution to the PvNP problem" Anand shows that
Goedel has defined an arithmetical tautology R(n) which - when treated as a
Boolean function - is constructively computable as true for any given natural
number n, but which is not Turing-computable as true for any given natural number n.
This then implies that P is not equal to NP.
In June 2008, Rafee Ebrahim Kamouna proved that P and NP coincide.
His proof first establishes (in contradiction to Cook's theorem) that SAT is in fact
not NP-complete, then observes that there are no NP-complete problems, and finally
deduces P=NP from this.
The paper"The Kleene-Rosser Paradox, The Liar's Paradox & A Fuzzy Logic
Programming Paradox Imply SAT is (NOT) NP-complete"
is available at
Additional information on this approach can be found at
(Thanks to Ronald Ortner for providing this link.)
[Not equal]:
In August 2008, Jerrald Meek proved that some NP-complete problems in fact are not
really NP-complete. Of course this implies that P is not equal to NP.
His paper "Analysis of the postulates produced by Karp's Theorem"
is the final article in a series of four articles.
It is available at
(Thanks to David Eppstein for providing this link.)
[Not equal]:
In September 2008, Jorma Jormakka proved that P is not equal to NP by showing that
the subset sum problem cannot be solved in polynomial time.
His paper "On the existence of polynomial-time algorithms to the subset sum problem"
is available at
[Not equal]:
In October 2008, Sten-Ake Tarnlund established that P is not equal to NP.
He shows that the statement "SAT is not in P" is true and provable in a simply
consistent extension B' of a first order theory B of computing, with a single
finite axiom characterizing a universal Turing machine.
His paper "P is not equal to NP"
is available at
Henning Makholm comments on Tarnlund's arguments in his
In September 2013, Sten-Ake Tarnlund announced an improved version of his argument.
His proofs are informal about formal proofs in a first-order theory B axiomatizing Turing's
theory of computing. However, the informal proofs can be converted into formal proofs in
Hilbert's proof theory, and proved using a theorem prover.
The improved version is available at
(Thanks to Chris Hodges for providing the link to Tarnlund's first paper, and
thanks to Thore Husfeldt for providing the link to Makholm.)
In November 2008, Zohreh O. Akbari proved that P is equal to NP.
Her paper "A Deterministic Polynomial-time Algorithm for the Clique Problem
and the Equality of P and NP Complexity Classes"
appeared in Volume 35 of the "Proceedings of World Academy of Science,
Engineering and Technology",
and is available at
Akbari designs a deterministic polynomial time algorithm for the NP-hard clique problem.
In 2013, an updated version of the paper was presented at the 2013 IEEE/ACIS 12th
International Conference on Computer and Information Science (ICIS), under the title
"A polynomial-time algorithm for the maximum clique problem".
The paper is available at
(Thanks to Andrew Fabbro and Austin Buchana for providing these links.)
In December 2008, Javaid Aslam proved that P is equal to NP.
His paper "The Collapse of the Polynomial Hierarchy: NP=P"
is available at
Aslam proves that counting of Hamiltonian Circuits in a given graph is in NC,
and that the Polynomial Hierarchy collapses.
Follow-ups:
by Frank Ferraro, Garrett Hall, Andrew Wood points out a flaw in the above paper.
Javaid Aslam's reaction to this refutation is available as
(Thanks to Lane A. Hemaspaandra for providing some of these links.)
In March 2009, Rafael Valls Hidalgo-Gato published an ICIMAF technical report
called "P=NP", with ISSN .
ICIMAF is the Institute of Cybernetics, Mathematics and Physics in Cuba, and
belongs to CITMA (the Cuban Ministry of Science, Technology and Ambient Medium).
This report was announced in March 2009 in the usenet newsgroup comp.theory,
but without providing any link to an electronic version.
The author also mentions that he actually has already resolved the P versus NP problem
in October 1985.
The result was published in the proceedings of the ININTEF (Institute of Fundamental
Technical Research, Cuban Academy of Science) Scientific Conference that took place
around that time at Capitol (Havana, Cuba).
The paper is "M&todo de soluci&n para sistemas de ecuaciones
simult&neas sobre un Campo de Galois y aplicaciones en Inteligencia Artificial"
(Solution method for systems of simultaneous equations over a Galois Field and
Artificial Intelligence applications), 1985 Annual Report, Vol.II, S2-25, p.274,
Cuban Academy of Science Edition.
As part of that paper, a polynomial-time algorithm is given that resolves an
NP-complete problem.
On the 1st of April 2009, Doron Zeilberger proved that P is equal to NP.
He provided a polynomial time algorithm for the Subset Sum problem.
Zeilberger translates the problem into evaluating an underlying integral.
He writes:
"Using rigorous interval analysis, rather than non-rigorous floatingpoint
computations, we can estimate the integral, as well as bound the error, thereby
solving the problem in 'polynomial' time.
The rigorous estimate of the error (crucial to the success of the decision algorithm),
involves solving more than ten thousand Linear Programming problems, each with more
than one hundred thousand variables.
This system was generated automatically and dynamically, using a genetic algorithm
and simulated annealing, as well as sophisticated Markov Chains and Bayesian analysis.
Of course, we do not guarantee that this is the shortest possible proof, since it was
generated by a non-determinstic Turing machine, but it is indeed a fully rigorous proof.
The validity of the proof was independently checked by four other computers, running on
different platforms and different programming languages."
The paper can be found at
At the end of April 2009, Doron Zeilberger wrote me:
[...] However, you should add that this was meant as an April Fool's Joke,
since apparently, some people didn't get that it was meant as a joke,
and while the paper has some valid general statements abouts humans,
the "proof" itself is complete gibberish (and of course, intentionally so).
(Thanks to Fred Wehrung for providing this link.)
In April 2009, Xinwen Jiang published a proof for P is equal to NP.
He provided an algorithm for the Hamilton circuit problem, and states
"It seems our algorithm is a polynomial one".
The paper can be found at
An earlier version of his paper was published in a Chinese journal in 2007.
Further versions have been published in 2010 and 2011.
More information on the current version of the proof is available at
Since May 2013, the paper "A Polynomial Time Algorithm for the Hamilton Circuit Problem" is available at
(Thanks to Maris Ozols for providing some of these links.)
[Not equal]:
In June 2009, Arto Annila proved that P is not equal to NP.
He writes:
The state space of a non-deterministic finite automaton is evolving due to the
computation itself hence it cannot be efficiently contracted using a deterministic
finite automaton that will arrive at a solution in super-polynomial time.
The solution of the NP problem itself is verifiable in polynomial time (P) because
the corresponding state is stationary. Likewise the class P set of states does not
depend on computational history hence it can be efficiently contracted to the
accepting state by a deterministic sequence of dissipative transformations.
Thus it is concluded that the class P set of states is inherently smaller than
the set of class NP.
Annila's paper "Physical portrayal of computational complexity"
is available at
The paper has also been published in the journal ISRN Computational Mathematics 2012 ID: -15,
and is available at
(Thanks to Matti Niemenmaa for providing some of these links.)
[Not equal]:
In July 2009, Andre Luiz Barbosa established that P is not equal to NP.
He constructed an artificial problem XG-SAT, and demonstrated that
it is in NP but not in P.
The paper "P != NP Proof"
is available at
In June 2011, Lane Hemaspaandra, Kyle Murray and Xiaoqing Tang analyzed and criticized Barbosa's results.
They point out some unclear/fuzzy parts and conclude that it is exceedingly unlikely that Barbosa's proof
can be fixed any time soon.
Their note "Barbosa, Uniform Polynomial Time Bounds, and Promises" is available at
(Thanks to Florian Sikora for providing the link to Barbosa's paper.)
In September 2009, Yann Dujardin proved that P and NP coincide.
The main result is a polynomial time algorithm for the NP-hard PARTITION problem.
The paper "R&solution du partition problem par une approche arithm&tique"
(written in French) is available at
(Thanks to Dirk Gerrits for providing this link.)
In September 2009, Luigi Salemi established that P is equal NP.
He considers 3SAT with n variables, and designs an algorithm with a polynomial
running time of O(n^11).
His paper "Method of resolution of 3SAT in polynomial time"
is available at
Some additional information (and a pdf-file explaining the spirit of the proof)
is available at the author's page
(Thanks to Dirk Gerrits for providing this link.)
[Not equal]:
In December 2009, Ari Blinder proved that P is not equal to NP.
He proves that there exists a language that is contained in NP, but not in co-NP.
This yields that NP is not equal co-NP, and of course implies that P is not equal to NP.
His paper "A Possible New Approach to Resolving Open Problems in Computer Science"
is available at
On 10-March-2010, Ari Blinder announced that he has found a hole in his proof.
In 2009, Narendra S. Chaudhari designed a constructive procedure for solving the 3-SAT
problem in polynomial time O(n^13).
The main trick lies in the representation that allows Chaudhari to cast the 3-SAT problem in
terms of the CLAUSES and not the literals.
The complexity is fundamentally different because the mapping from literals to clauses is
exponential while from clauses to 3-SAT is linear.
The paper "Computationally Difficult Problems: Some Investigations"
has appeared in the Journal of the Indian Academy of Mathematics Vol 31, 4.
A copy is available
(Thanks to Ryan Williams for providing this link.)
In April 2010, Lizhi Du proved that P=NP by constructing a polynomial time algorithm for
finding a Hamilton Cycle in an undirected graph.
The paper describes the algorithm, its proof, and the experimental data.
It is called "A Polynomial Time Algorithm for Hamilton Cycle and Its Proof",
and it is available at
(Thanks to Dirk Gerrits for providing this link.)
In May 2010, Changlin Wan proved that P=NP.
The central idea of the proof is a recursive definition for Turing machine (shortly TM).
The paper is called "A Proof for P vs. NP Problem",
and is available at
(Thanks to Dirk Gerrits and Florian Sikora for providing this link.)
[Not equal]:
In June 2010, Carlos Barron-Romero established P not equal to NP.
His paper "The Complexity Of The NP-Class" presents a novel and straight formulation,
and gives a complete insight towards the understanding of the complexity of the problems of
the so called NP-Class.
The paper is available at
(Thanks to Jean Baylon and Dirk Gerrits for providing this link.)
In June 2010, Han Xiao Wen proved that P=NP.
His paper "Mirrored Language Structure and Innate Logic of the Human Brain as
a Computable Model of the Oracle Turing Machine"
suggests an algorithm of relation learning and recognition (RLR) that enables the
deterministic computers to simulate the mechanism of the Oracle Turing machine,
or P=NP in a mathematical term.
This paper is available at
In September 2010, Han Xiao Wen provided another proof that P=NP in the
paper "Knowledge Recognition Algorithm enables P = NP".
The paper is available at
(Thanks to Juraj Burian for providing some of these links.)
In July 2010, Mikhail Katkov established P=NP.
His paper "Polynomial complexity algorithm for Max-Cut problem" formulates the
NP-hard Max-Cut problem as a semi-definite program.
The paper is available at
Additional information on this approach can be found at
(Thanks to Dirk Gerrits and Michael Thomas for providing this link.)
[Not equal]:
In the beginning of August 2010, Vinay Deolalikar announced a proof that
P is not equal to NP.
He writes:
"The proof required the piecing together of principles from multiple areas within
mathematics.
The major effort in constructing this proof was uncovering a chain
of conceptual links between various fields and viewing them through a common lens.
Second to this were the technical hurdles faced at each stage in the proof.
This work builds upon fundamental contributions many esteemed researchers have made
to their fields. In the presentation of this paper, it was my intention to provide
the reader with an understanding of the global framework for this proof.
and computational details within chapters were minimized as much as possible."
The first version of the paper "P!=NP" had 66 pages, and is available as
Lots of useful discussions on this proof:
In August 2010, Sergey Gubin proved that the ATSP (Asymmetric Travelling Salesman Polytope)
can be expressed by an asymmetric linear program of polynomial size.
This implies P=NP.
His paper "Complementary to Yannakakis' theorem" has been published in Volume 74
of The Journal of Combinatorial Mathematics and Combinatorial Computing on pages
And here is a
of Gubin's arguments by Romeo Rizzi from January 2011.
In November 2010, Vladimir Romanov proved P=NP.
His paper "Non-Orthodox Combinatorial Models Based on Discordant Structures"
introduces a novel method for compact representation of sets of n-dimensional
binary sequences in a form of compact triplets structures (CTS), supposing
both logic and arithmetic interpretations of data.
It is available at
Additional information can be found at
(Thanks to Dirk Gerrits for providing this link.)
[Not equal]:
In November 2010, Frank Vega Delgado proved that P is not equal to NP, by investigating
an algorithmic problem called CERTIFYING.
On the one hand, CERTIFYING lies in NP.
On the other hand, if CERTIFYING would belong to P then NP would also contain some undecidable problem (which is impossible).
The paper "A Solution to the P versus NP Problem" is available at
(Thanks to Florian Sikora for providing this link.)
[Not equal]:
In December 2010, Carlos Barron-Romero established that P is not equal to NP.
His paper "The Complexity of Euclidian 2 Dimension Travelling Salesman Problem
versus General Assign Problem, NP is not P" focuses on the Euclidian 2-dimensional
Travelling Salesman Problem and the General Assignment Problem, and presents the
differences between these two NP problems.
The paper is available at
(Thanks to Mathieu Chapelle for providing this link.)
[Not equal]:
In December 2010, Bangyan Wen and Yi Lin proved that P is not equal to NP.
Their paper "THE ANSWER TO THE P/NP PROBLEM IS P&NP! settles the question by using
formal logic reasoning and analysis.
The paper was published in the electronic journal
"Scientific Inquiry - A Journal of the IIGSS" (International Institute for General System Studies),
and it is available from
(Thanks to Jeffrey Forrest for providing this link.)
[Not equal]:
In January 2011, Ruijia Liao established that P is not equal to NP, by
using algorithms and pseudo-algorithms.
His paper "The Complexity of 3SAT_N and the P versus NP Problem" is available at
(Thanks to Guillaume Aupy for providing this link.)
[Equal] and [Not equal]:
In April 2011, Stefan Jaeger proved that P equals NP (under the first Peano axiom) and that
P is not equal to NP (without the first Peano axiom).
The paper "Computational Complexity on Signed Numbers" presents a new representation of
natural numbers and discusses its consequences for computability and computational complexity.
It is available at
In April 2011, Amar Mukherjee proved that P equals NP, by presenting a deterministic
polynomial-time algorithm for the 3-satisfiability problem.
The paper "The 3-satisfiability problem" is available at
(Thanks to Florian Sikora for providing this link.)
In spring 2011, Angela Weiss established P=NP by presenting a polynomial-time algorithm for
the 3-satisfiability problem.
The approach uses classical KE-tableaux methods to built a macro that stores the relevant
data (all closed branches) for a tableau for a given 3-sat formula.
The paper "A Polynomial Algorithm for 3-sat" is available from
This page also contains a discussion group on that proof.
In June 2011, Matt Groff established P=NP through an O(n^7) time algorithm for the
satisfiability problem.
The paper "Towards P = NP via k-SAT: A k-SAT Algorithm Using Linear Algebra on Finite Fields"
is available at
(Thanks to Serguei Mokhov and Arne Meier for providing this link.)
In July 2011, Sergey Kardash proved P=NP by designing an O(n^12) time algorithm for 3-SAT.
His paper "Algorithmic complexity of pair cleaning method for k-satisfiability problem"
is available at
(Thanks to Hongyu Liang for providing this link.)
[Not equal]:
In September/October 2011, Anatoly Plotnikov proved that P is not equal to NP.
The paper "On the relationship between classes P and NP" constructs a class UF that contains P,
and that simultaneously is strictly contained in NP; the proof is available at
His papers "About set-theoretic properties of one-way functions"
(available at )
and "On the structure of the class NP"
(available at )
provide further analysis of this class UF.
(Thanks to Igor Razgon and Florian Sikora for providing these links.)
[Not equal]:
In October 2011, Koji Kobayashi showed that P is not equal to NP, by building the language CHAOS in NP\AL.
The paper "NP is not AL and P is not NC is not NL is not L" is available at
(Thanks to Jean-Marie Madiot for providing this link.)
In October 2011, Jason W. Steinmetz established P=NP.
His paper "Algorithm that Solves 3-SAT in Polynomial Time"
presents a polynomial time solution for the NP-hard 3-SAT problem.
It is available at
(Thanks to Bertrand Collet, Anthony Labarre and Florian Sikora for providing this link.)
In October 2011, Jose Ignacio Alvarez-Hamelin proved P equals NP.
He presents an efficient algorithm for computing a maximum clique in general graphs.
His paper "Is it possible to find the maximum clique in general graphs?" is available at
(Thanks to Dirk Gerrits for providing this link.)
[Not equal]:
In November 2011, Roman Yampolskiy proved that P is not equal to NP, by constructing a variant of
the Travelling Salesman Problem (the so-called Hashed-Path Traveling Salesperson Problem, HPTSP).
Yampolskiy shows that HPTSP has the interesting property of having no polynomial time solution.
Furthermore he shows that HPTSP is in the class NP by demonstrating that local information about
sub-routes is insufficient to compute the complete value of each route.
The paper "Construction of an NP Problem with an Exponential Lower Bound" is available at
(Thanks to Arne Meier for providing this link.)
[Not equal]:
In November 2011, Craig Alan Feinstein proved that P is not equal to NP.
The argument is surprisingly short.
It essentially shows that the Traveling Salesman Problem cannot be solved in polynomial-time on a classical computer.
The paper "The Computational Complexity of the Traveling Salesman Problem" is available at
(Thanks to Joshua Lockhart and Mathieu Chapelle for providing this link.)
[Not equal]:
In fall 2011, Jeffrey W. Holcomb established P!=NP.
The website
a sequence of papers that together establish P!=NP.
seems to be a particularly important one.
The proof relies upon the existence of stochastic answers in the set difference between NP and P.
(Thanks to Peter Bro Miltersen for providing these links.)
In January 2012, Douglas Youvan established P=NP in a certain model (that seems to allow time travelling).
The Kindle edition of his book
"As Velocity Approaches Light Speed, P Becomes Equivalent to NP for Computations Using Zero-Mass Particles"
is available for sale at
(Thanks to Gabriel Istrate for providing this link.)
[Not equal]:
In January 2012, Gilberto Rodrigo Diduch proved that P is not equal to NP.
states that the
answer to the P vs NP question is a categorical NO; these classes are different as their names suggest.
Diduch's paper has been published in the International Journal of Computer Science and Network Security
(), Volume 12, pages 165-167.
(Thanks to Gordon Royle for providing the link.)
[Not equal]:
In February 2012, Koji Kobayashi proved that P is not equal to NP.
His paper "Topological approach to solve P versus NP" shows that there are some CNF formulas
that cannot be reduced to HornCNF formulas of polynomial size.
It is available at
[Not equal]:
In February 2012, Frank Vega Delgado proved that P is not equal to NP.
He starts from the assumption P=UP, and shows that this leads to EXP=P (which is known to be wrong from
the time hierarchy theorem); this contradiction implies that P is not equal to UP (which
forms a subclass of NP).
His paper "The existence of one-way functions" is available at
A variant of the proof appeared under the title "P versus UP" in the
Yet another variant of the paper "P versus UP" was submitted to the arXiv under the
pseudonym Asia Furones.
The paper at
has been withdrawn by arxiv admin, due to use of pseudonym by frank.vega@datys.cu against arXiv policy.
Some older versions can still be accessed at
(Thanks to Iris Delgado, Juraj Burian and Thomas Klimpel for providing some of these links.)
[Not equal]:
In March 2012, Minseong Kim showed that the Zermelo-Fraenkel axioms of set theory together with the axiom of
choice are inconsistent, and then deduced from this that P is not equal to NP.
"Inconsistency of the Zermelo-Fraenkel set theory with the axiom of choice and its effects on the computational
complexity" is available at
(Thanks to Gabriel Istrate for providing this link.)
In March 2011, Algirdas Antano Maknickas proved that P=NP.
His paper "How to solve kSAT in polynomial time"
uses multi-nary logic analytic formulas in modulo form to derive a polynomial time problem
for the NP-hard k-Satisfiability problem.
The conclusions of the paper are that every mathematical problem is solvable in polynomial time if
exist full, appropriate and correct knowledge basis for it and the time to get each item of knowledge
basis is match less than calculation time on this items.
The paper is available at
(Thanks to Juraj Burian for providing this link.)
In May 2012, Michel Feldmann established P=NP.
His paper "From classical versus quantum algorithms to P versus NP"
reduces 3-SAT to a linear programming problem, while introducing Bayesian probability theory in classical computation.
According to algorithmic complexity theory this proves that P=NP.
The paper is available at
(Thanks to Anthony Leverrier, Gr&gory Strubi
and Javaid Aslam for providing this link.)
[Not equal]:
In summer 2012, Junichiro Fukuyama from the Toyota InfoTechnology Center proved that P is not equal to NP.
The proof explores topological properties of a Hamming space, generalizes the sunflower lemma, and builds on circuit theory.
The paper "Computing Cliques is Intractable" is available at
In May 2013, the author made his proof also available on the ArXive, at
(Thanks to Uri Segal and Maris Ozols for providing these links.)
[Not equal]:
In July 2012, Satoshi Tazawa proved that P is not equal to NP.
The proof establishes that the decision problem version of integer factorization problem is neither in P nor NP-complete.
From this result, the conclusion that P is not NP is reached.
The paper "Integer factorization and Discrete Logarithm problem are neither in P nor NP-complete" is available at
Later versions of this paper carry the title "Relationship between circuit complexity and symmetry".
The paper shows that by interpreting a Boolean circuit as a graph, the small number of graph automorphisms and the large
number of subgraph automorphisms in the circuit establishes the exponential circuit lower bound for NP-complete problems.
As this strategy violates the largeness condition in Natural proof, this result shows that P!=NP without any contradictions
to the existence of pseudorandom functions.
(Thanks to Adam Scherlis for providing these links.)
In July 2012, Wen-Qi Duan proved that P=NP.
His paper "A Constructive Algorithm to Prove P=NP"
first reduces the undirected Hamiltonian cycle problem into the TSP problem with cost 0 or 1, and then
develops an effective algorithm to compute the optimal tour of the transformed TSP.
This yields a polynomial time algorithm for the undirected Hamiltonian cycle problem, and established P=NP.
The paper is available at
In September 2012, Sergey V. Yakhontov proved that P=NP.
The proof is constructive, and explicitly gives a polynomial time deterministic algorithm that determines whether
there exists a polynomial-length accepting computational path for a given non-deterministic single-tape Turing machine.
The paper is available at
(Thanks to Ricardo Mota Gomes for providing this link.)
[Unprovable]:
In November 2012, Natalia L. Malinina put the paper "On the principal impossibility to prove P=NP"
onto the arxive, at .
On page 19, she writes: "Summarizing all that was said, it can be concluded that such dividing of
the graphs into three classes and the behavior of the complicated vertexes at the converting (they turn into
the independent cycles) gives us the infallible fact that it is impossible to prove that P=NP."
(Thanks to Freek van Walderveen for providing this link.)
In December 2012, Louis Coder proved that P=NP.
The proof designs an algorithm that determines the solvability state (solvable
or unsatisfiable) of any exact-3-SAT formula in polynomial time.
The paper Polynomial Exact-3-SAT Solving Algorithm is available as pdf on
In December 2013, Louis Coder designed a new version of his algorithm.
The paper "Polynomial SAT-Solver - Algorithm Explanation" is available
as pdf on vixra.org as well.
In January 2013, Dmitriy Nuriyev established P=NP.
His paper "A DP Approach to Hamiltonian Path Problem" designs a polynomial worst case time Dynamic Programming algorithm
for computing a Hamiltonian Path in a directed graph.
The result is obtained via the use of original colored hypergraph structures in order to maintain and update the necessary DP states.
The running time of the resulting algorithm is O(n^8) where n denotes the number of vertices in the directed graph.
The paper is available at
(Thanks to Florian Sikora for providing this link.)
In March 2013, the International Conference on Advances in Engineering Technologies and Physical Science
was held in Hong Kong.
The proceedings of this conference have been published by the respected publishing house Springer Science,
and contain the paper Linear Programming Formulation of Boolean Satisfiability Problem by Algirdas Antano Maknickas.
Maknickas translates the (NP-hard) satisfiability problem into a (polynomially solvable) linear programming
This of course implies P=NP.
The paper is available at
(Thanks to Ruben Ruiz Torrubiano for providing this link.)
[Not equal]:
In August 2013, Rustem Chingizovich Valeyev established that P is not equal to NP.
The proof shows that the most effective algorithm for the TSP is exhaustive search, and hence
an expone this of course implies that P is not equal to NP.
The paper "The Lower Border of Complexity of Algorithm of the Elementary NP-Complete Task (The Most Condensed Version)"
has been published in Volume 8 of the
and is available as
In October 2013, Frederic Gillet showed that P=NP.
He shows how the implementation of conservative logic gates on flow networks allows us to solve 3SAT
and 3-dimensional matching problems in polynomial time by using standard minimum-cost flow methods.
The paper "Solving 3-SAT and 3-dimensional matching in polynomial time"
is available at
Addendum. In November 2013, the author added the following comment to the arxive page:
The proposed method does not work. Updated the article with an analysis of why the general method
suggested cannot work. Will withdraw the paper once this updated version is loaded.
In January 2014, Hanlin Liu established P=NP by constructing a polynomial time algorithm for the
Hamiltonian circuit problem in a graph G=(V,E); the algorithm has a time complexity of O(|V|^9).
The paper "A Algorithm for the Hamilton Circuit Problem" is available at
In February 2014, Pawan Tamta, B.P. Pande and H.S. Dhami proved P=NP by constructing a polynomial
time algorithm for the clique problem.
They show that the Clique Problem has a reduction to the Maximum Flow Network Interdiction Problem,
and they review the reduction to evolve a polynomial time algorithm for the clique problem.
The paper "A Polynomial Time Solution to the Clique Problem" is available at
In April 2015, Hector A. Cardenas, Chester Holtz, Maria Janczak, Philip Meyers, Nathaniel S. Potrepka
published a refutation of this approach.
Their paper "A Refutation of the Clique-Based P=NP Proofs of LaPlante and Tamta-Pande-Dhami"
is available at
(Thanks to Florian Sikora, Lane Hemaspaandra, and Kirk Pruhs for providing some of these links.)
In February 2014, Peng Cui proved P=NP.
The main ingredients of the paper include a key issue in dictator test that disguises the questions
of the verifier to a balanced pairwise independent distribution and a variance-style theorem to eliminate
correlation of answers of all players based on Label-Cover and its reflection version, which does not
rely on the technique of direct sum that requires the subgroup property.
On the other hand, the author shows that the gap problem of this type of k-CSP can be solved by a SDP
algorithm in polynomial time efficiently, when the support of C is combined by the grounds of three
truncated biased pairwise independent distributions and the three biases satisfy certain conditions.
The paper "Approximation Resistance by Disguising Biased Distributions is available at
[Not equal]:
In February 2014, Daegene Song established that P is not equal to NP.
The main idea is to consider P (respectively NP) as a class of deterministic (respectively nondeterministic)
polynomial-time physical processes, and to exhibit a physical process in quantum theory which belongs to NP
but cannot be contained in P.
The paper "The P versus NP Problem in Quantum Physics" is available at
[Not equal]:
In March 2014, Joonmo Kim proved that P is not equal to NP.
The proof uses an artificially designed Turing Machine that generates the instances of the satisfiability problem,
and checks their satisfiability. Under the assumption P equal NP, this machine has a certain property, which it does
not have without the assumption. This leads to P not equal NP, by modus tollens.
The paper "P not equal NP by modus tollens" is available at
In April 2014, Dan Hassin, Adam Scrivener and Yibo Zhou note that the logic that Kim uses is inconsistent
and provide evidence that the proof is invalid.
Their findings are available at
(Thanks to Szabolcs Ivan for providing these links.)
In September 2014, Anatoly Panyukov proved P=NP by constructing a polynomial time algorithm
for the Hamiltonian circuit problem.
The paper "Polynomial solvability of NP-complete problems" is available at
(Thanks to Falk H&ffner and Florian Sikora for providing this link.)
In March 2015, Michael LaPlante established P=NP by constructing a polynomial time algorithm
for the maximum clique problem in a graph.
The paper "A Polynomial Time Algorithm For Solving Clique Problems" is available at
In April 2015, Hector A. Cardenas, Chester Holtz, Maria Janczak, Philip Meyers, Nathaniel S. Potrepka
published a refutation of this approach.
Their paper "A Refutation of the Clique-Based P=NP Proofs of LaPlante and Tamta-Pande-Dhami"
is available at
(Thanks to Santanu Bhowmick, Adam Kurpisz, Florian Sikora, Lane Hemaspaandra, and Kirk Pruhs and
several others for providing these links.)
In April 2015, Alejandro Sanchez Guinea established P=NP by designing
an algorithm which takes a logical formula in conjunctive normal form, terminates
successfully iff the formula is satisfiable, and runs in polynomial time.
This implies P=NP.
The paper "Understanding SAT is in P"
is available at
(Thanks to Szabolcs Ivan for providing these links.)
In June 2015, Frank Vega introduced a new complexity class (called equivalent-P), which
has a close relation to the P-versus-NP question.
The class equivalent-P has those languages that contain ordered pairs of instances, where each
one belongs to a specific problem in P, such that the two instances share a same solution, that
is, the same certificate.
Vega then demonstrates that (i) equivalent-P = NP and (ii) equivalent-P = P.
These two statements clearly imply P=NP.
The paper "Solution of P versus NP Problem"
is available at
In October 2015, Yubin Huang proved the following:
For any language L accepted by a non-deterministic Turing machine in polynomial time, there exists a
deterministic Turing machine that accepts L in polynomial time.
A restricted Turing machine, whose maximum number of nondeterministic moves in the accept computation
tree of inputs is limited, is constructed and studied.
This limitation establishes a hierarchy of classes associated with natural numbers between P and NP.
Any language in NP is also accepted by machines in each of these classes, and P forms the lowest hierarchy level.
The paper "Testing a new idea to solve the P = NP problem with mathematical induction"
is available at
[Not equal]:
In January 2016, Daniel Uribe proved that P is not equal to NP.
The method for analyzing algorithmic runtime complexity using decision trees is discussed using
the sorting algorithm. This method is then extended to optimal algorithms which may find all
cliques of size q in network N, or simply the first clique of size q in network N. Finally, the
lower bound of such decision trees is demonstrated to not be in P.
The paper "P vs. NP"
is available at
In February 2016, Frank Vega established a closely related result: He showed that P=NP implies P=EXP.
Since P is not equal to EXP, this yields that P is not equal to NP.
The paper "Is P equal to NP?"
is available at
(Thanks to Hans Georg Sedig, Clyde Kruskal, and others for providing these links.)
[Not equal]:
In February 2016, Mathias Hauptmann showed that P is not equal to NP.
Hauptmann starts from the assumption that P equals Sigma-2-p, proves a new variant of the
Union Theorem of McCreight and Meyer for Sigma-2-p, and eventually derives a contradiction.
This implies P not equal to NP.
The paper "On Alternation and the Union Theorem" is available at
(Thanks to Rolf Niedermeier and Ryan Dougherty for providing these links.)
In March 2016, Steven Meyer established P=NP.
Meyer solves the P-versus-NP problem philosophically by showing P is equal to NP in the random
access with unit multiply (MRAM) model.
More precisely, the P-versus-NP problem is shown to be a scientific rather than a mathematical problem.
The assumptions involved in the current definition of the P-versus-NP problem as a problem involving
non deterministic Turing Machines (NDTMs) from axiomatic automata theory are criticized.
The problem is also shown to be neither a problem in pure nor applied mathematics.
The paper "Philosophical Solution to P=?NP: P is Equal to NP" is available at
(Thanks to Samuli Lepp&nen for providing these links.)
[Not equal]:
In April 2016, Javier A. Arroyo-Figueroa showed that P is not equal to NP.
Arroyo-Figueroa establishes the existence of a certain class of one-way functions that are
(i) computable in polynomial time and (ii) with negligible probability of finding its inverse
by any polynomial probabilistic algorithm.
This is accomplished by constructing each member in T with a collection of independent universal
hash functions that produce a starting coordinate and a path within a sequence of unique
random bit matrices.
The existence of one-way functions implies that P is not equal to NP.
The paper "The Tau One-Way Functions Class: P != NP" is available at
(Thanks to Szabolcs Ivan and Christian Lidstr&m for providing these links.)
In summer 2016, Eli Halylaurin showed P=NP.
The main result is that PSPACE is included in P. Because it is already known that P
is included in NP and NP is included in PSPACE, this implies the desired P=NP.
The paper "An Attempt to Demonstrate P=NP" is available at
[Not equal]:
In September 2016, Stefan Rass showed that weak one-way functions exist.
These are constructed as preimages of sequences of decision problem instances that are
sampled randomly by means of an explicit threshold function.
As a consequence, P is not equal to NP.
The paper "On the Existence of Weak One-Way Functions is available at
(Thanks to
Andras Salamon for providing these links.)
I am interested in extending this list.
If you know of other papers in this area, then please send me the links.
Maintained by
Revised: 26 September 2016}