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:

• A clear formulation of the "P versus NP" question by Stephen Cook.
• Mathworld's page on "P versus NP"
• The Wikipedia page on "P versus NP"
• Michael Sipser has a survey paper on "The History and Status of the P versus NP question" (Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 603-619).
• Christos Papadimitriou has written a retrospective on NP-completeness
• Lance Fortnow and Steve Homer: A Short History of Computational Complexity
• Scott Aaronson: Is P Versus NP Formally Independent? and NP-complete Problems and Physical Reality

Here is the outcome of an opinion poll on "P versus NP" conducted by William Gasarch.
Here are the reasons why Oded Goldreich refuses to proof-read papers settling the "P versus NP" question.
Here is what googlism thinks of "P versus NP" and "P=NP".
Here is a parody of a typical comp.theory newsgroup discussion of a typical P=/!=NP proof.
Here is Homer Simpson on "P versus NP" (picture #1 / #2)
Here is a (youtube) movie on P and NP.

New proof by Vinay Deolalikar

The paper "P!=NP" has 66 pages, and is available as pdf-file.
An updated version is available as updated pdf-file.
Lots of useful discussions on this proof: http://rjlipton.wordpress.com/

Milestones

1. [Equal]: 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 size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.
   

2. [Equal]: The 1996 issue (Volume 1, 1996, pp. 16-29) of the "SouthWest Journal of Pure and Applied Mathematics" (SWJPAM) contains the article "Polynomial-Time Partition of a Graph into Cliques" by the Ukrainian mathematician Anatoly Plotnikov. 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.)
   

3. [Equal]: 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 "Hardness and methods to solve CLIQUE" (Journal of Computer Science and Technology 16, 2001, pp 388-391).
   

4. [Equal]: Here is Miron Telpiz's web-page 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)".
   

5. [Not equal]: The 3rd International Conference on Information and Communications Security (ICICS 2001) took place in Xian, China, November 13-16, 2001. The proceedings of ICICS 2001 have been published as Volume 2229 of Springer Lecture Notes in Computer Science. Pages 495-501 of these proceedings contain the paper "Redundancy, Obscurity, Self-Containment & Independence" by Seenil Gram; 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 explanations on his breakthrough result in the newsgroup "sci.crypt".
   (Thanks to Daniel Marx for providing this link.)
   

6. [Equal]: 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. The paper "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.
   

7. [Equal]: Here is a link to a paper 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 summary.
   

8. [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: ascii file
   (Thanks to Daniel Marx for pointing me to this result.)
   

9. [Unprovable]: The journal "Applied Mathematics and Computation" (AMC) 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 article "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.
   Here is a review of this proof by the German logician Ralf Schindler. Andreas Blass, the reviewer of this paper in the AMS Mathematical Reviews, writes in his review MR2009291 (2004f: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 [...]."
   

10. [Not equal]: Hubert Chen has a webpage (2003) 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."
    

11. Here is a link to the paper "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 paper "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".
    

12. [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" in the 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 to P=NP.
    Richard K. Molnar, the reviewer of this paper in the AMS Mathematical Reviews, writes in his review MR2038228 (2005e: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.)
    

13. [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 pdf-file #1; pdf-file #2; pdf-file #3.
    

14. [Equal]: Here is another paper 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.)
    

15. Here is a link to the web-page of Bhupinder Singh Anand. In his essay "Some consequences of defining mathematical objects constructively and mathematical truth effectively" (submitted to Philosophia Mathematica), he 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.
    

16. [Not equal]: Marius Ionescu has written a paper 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 http://1wayfx.com 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.)
    

17. [Equal]: 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 http://www.business.uconn.edu/users/mdiaby/tsplp/. 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 http://arxiv.org/abs/cs/0609005 (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 http://www.business.uconn.edu/users/mdiaby/qaplp/. A new version of the paper can be found at http://arxiv.org/abs/cs.CC/0609004 (uploaded: 2 Sep 2006). A version of the QAP paper has been published in the 2006 IMECS Conference Proceedings (ISBN: 988-98671-3-3). 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 Linear programming formulation of the vertex colouring problem and Linear programming formulation of the set partitioning problem give linear programming formulations for two well-known NP-hard problems. Both papers were published in the "International Journal of Operational Research (IJOR)". They are also available as pdf-file #1 and pdf-file #2.
    (Thanks to Philipp Lucas, Philippe Schnoebelen, and Ugo Vaccaro for providing some of these links.)
    

18. [Not equal]: In November 2004, Mircea Alexandru Popescu Moscu introduced an invariance principle of complexity hierarchies. His paper is available at http://arxiv.org/abs/cs.CC/0411033 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".
    

19. [Equal]: 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. More information on his approach is available at http://www.bianchiniandrea.it/abssp.asp, and the underlying theory is explained in this pdf-file.
    (Thanks to Philip Bille for providing this link.)
    

20. [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 http://arxiv.org/abs/cs/0502030. 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.)
    

21. [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 pdf-file for this paper.
    And here is a newer version of this paper "NP versus P problem: A proof that NP is not equaled to P", dating from spring 2010.
    

22. [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 pdf-file from math.GM/0506126. 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.)
    

23. [Not equal]: In July 2005, Craig Alan Feinstein wrote the paper "Complexity Theory for Simpletons". 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 "Complexity science for simpletons" in Progress in Physics, July 2006. Progress in Physics 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.)
    

24. [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 his web-page at the University of Tuebingen (Germany), in particular the two papers "Proof-sketch: Why NP is not P" and "Combinatorial sentence that infers P < NP".
    (Thanks to Omar Al-Khayyam for providing these links.)
    

25. [Equal]: 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 here.
    (Thanks to Moritz Hammer for providing this link.)
    

26. [Equal]: In November 2005, Francesco Capasso constructed a polynomial-time algorithm for Circuit-SAT. This implies P=NP. The paper is available at http://arxiv.org/abs/cs.CC/0511071. 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.)
    

27. [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 http://www.arxiv.org/abs/cs.CC/0511085. 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.)
    

28. [Equal]: 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 http://www.tarusa.ru/~mit/ENG/sigma01_e.php.
    

29. [Equal]: 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 http://www.merlins-world.de/.
    

30. [Not equal]: In March 2006, Bhupinder Singh Anand proved that P is not equal to NP: http://arxiv.org/abs/math.GM/0603605. 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.
    

31. [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 http://arxiv.org/abs/cs.CC/0607093. 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 "Critique of Feinstein's Proof that P is not Equal to NP" by Kyle Sabo, Ryan Schmitt, and Michael Silverman.
    (Thanks to Luca Trevisan and Clyde P. Kruskal for providing these links.)
    

32. [Equal]: 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 http://www.wbabin.net/science/mimouni.pdf.
    Here are some comments by Radoslaw Hofman on this proof.
    

33. [Equal]: 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 http://arxiv.org/abs/cs.DM/0610042. The title of the paper is "A Polynomial Time Algorithm for The Traveling Salesman Problem".
    Here are some comments by Radoslaw Hofman on this proof.
    And here is a full refutation 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.)
    

34. [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 http://arxiv.org/abs/0704.0514.
    

35. In November 2006, Raju Renjit proved that co-NP is equal to NP: http://arxiv.org/abs/cs.CC/0611147. 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.
    

36. [Not equal]: In November 2006, Rubens Ramos Viana proved that P is not equal to NP: http://arxiv.org/abs/quant-ph/0612001. 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.
    

37. [Equal]: In December 2006, Howard Kleiman proved that P is equal to NP: http://arxiv.org/abs/math.CO/0612114. 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.
    

38. [Equal]: In 2006, Khadija Riaz and Malik Sikander Hayat Khiyal proved that P is equal to NP: http://www.scialert.net/pdfs/itj/2006/851-859.pdf. 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.)
    

39. [Equal]: In summer 2007, Guohun Zhu proved that P is equal to NP: http://arxiv.org/abs/0704.0309v3. 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. This page contains an outline of the argument.
    

40. [Equal]: (a) In August 2007, Matthew Delacorte proved that he graph isomorphism problem is PSPACE-complete: http://arxiv.org/abs/0708.4075. 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: http://arxiv.org/abs/0711.2010. 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.)
    

41. [Not equal]: In April 2008, Jerrald Meek proved that P is not equal to NP: http://arxiv.org/abs/0804.1079. 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.
    

42. [Not equal]: In June 2008, Bhupinder Singh Anand proved that P is not equal to NP (pdf-file). 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.
    

43. [Equal]: 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 http://arxiv.org/abs/0806.2947.
    (Thanks to Ronald Ortner for providing this link.)
    

44. [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 http://arxiv.org/abs/0808.3222.
    (Thanks to David Eppstein for providing this link.)
    

45. [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 http://arxiv.org/abs/0809.4935.
    

46. [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 http://arxiv.org/abs/0810.5056.
    Henning Makholm comments on Tarnlund's arguments in his blog.
    (Thanks to Chris Hodges for providing the link to Tarnlund, and thanks to Thore Husfeldt for providing the link to Makholm.)
    

47. [Equal]: 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 http://www.waset.org/pwaset/v35/v35-74.pdf. Akbari designs a deterministic polynomial time algorithm for the NP-hard clique problem.
    (Thanks to Andrew Fabbro for providing this link.)
    

48. [Equal]: 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 http://arxiv.org/abs/0812.1385. Aslam proves that counting of Hamiltonian Circuits in a given graph is in NC, and that the Polynomial Hierarchy collapses.
    

49. [Equal]: In March 2009, Rafael Valls Hidalgo-Gato published an ICIMAF technical report called "P=NP", with ISSN 0138-8916. 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.
    

50. [Equal]: 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 http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/pnp.pdf.
    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.)
    

51. [Equal]: 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 http://xinwenjiang.googlepages.com/. An earlier version of his paper was published in a Chinese journal in 2007.
    

52. [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 http://arxiv.org/abs/0906.1084.
    (Thanks to Matti Niemenmaa for providing this link.)
    

53. [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 http://arxiv.org/abs/0907.3965.
    (Thanks to Florian Sikora for providing this link.)
    

54. [Equal]: 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 http://arxiv.org/abs/0909.3466.
    (Thanks to Dirk Gerrits for providing this link.)
    

55. [Equal]: 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 http://arxiv.org/abs/0909.3868.
    (Thanks to Dirk Gerrits for providing this link.)
    

56. [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 http://sites.google.com/site/ariblindercswork/.
    On 10-March-2010, Ari Blinder announced that he has found a hole in his proof.
    

57. [Equal]: 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, 2009, 407-444. A copy is available here.
    (Thanks to Ryan Williams for providing this link.)
    

58. [Equal]: 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 http://arxiv.org/abs/1004.3702.
    (Thanks to Dirk Gerrits for providing this link.)
    

59. [Equal]: 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 http://arxiv.org/abs/1005.3010.
    (Thanks to Dirk Gerrits and Florian Sikora for providing this link.)
    

60. [Equal]: In June 2010, Carlos Barron-Romero established P=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. His main result is a polynomial time algorithm for the two-dimensional Euclidean Travelling Salesman Problem. The paper is available at http://arxiv.org/abs/1006.2218.
    (Thanks to Jean Baylon and Dirk Gerrits for providing this link.)
    

61. [Equal]: 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 http://arxiv.org/abs/1006.2495.
    

62. [Equal]: 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 http://arxiv.org/abs/1007.4257.
    Here is a comment by Omar Larré on Katkov's proof.
    (Thanks to Dirk Gerrits and Michael Thomas for providing this link.)

I am interested in extending this list. If you know of other papers in this area, then please send me the links.