P-vs-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) .

Scott Aaronson: Is P Versus NP Formally Independent?

Scott Aaronson Can NP-complete problems be solved efficiently in the physical universe?

Avi Wigderson, P, NP and Mathematics - a computational complexity perspective.

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.

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 mathematicianAnatoly 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.)

In May 2002 Charles Sauerbierdesigned 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. Thepaper "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 paper byGivi 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.

Nicholas Argallproved 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.)

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 logicianRalf 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 [...]."

Here is a link to the paper "Evidence that P is not equal to NP" byCraig 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".

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.)

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 http://arxiv.org/abs/1510.04225 .

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.)

In October 2004, Moustapha Diabyconstructed 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)". 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 http://www.worldscientific.com/worldscibooks/10.1142/9725 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 �sterg�rd, Philippe Schnoebelen, and Ugo Vaccaro for providing some of these links.)

In November 2004,Mircea Alexandru Popescu Moscuintroduced 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"..

In January 2005 Andrea Bianchiniproved 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 aspdf . (Thanks to Philip Bille for providing some pointers.).

In February 2005, Raju Renjit Groverr 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.)

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. In 2014, a new version of the proof has been published in the International Journal of Pure and Applied Mathematics IJPAMThe paper is available at the following link(Thanks to Boaz Barak for providing this link.)

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-filefrom 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.)

In July 2005 Craig Alan FeinsteinCraig Alan Feinstein "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.)

In Summer 2005, 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 web-page.at the University of Tuebingen (Germany), and in particular "Proof-sketch: Why NP is not P". (Thanks to Omar Al-Khayyam and Sebastian Schoener for providing these links.).

In October 2005 Lokman Kolukisadesigned 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.)

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.)

In November 2005, Ron Cohenproved 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.)

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 .

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/

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.

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. The final version of this paper appeared under the titel "An Elegant Argument that P≠NP" 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 http://www.wbabin.net/science/mimouni.pdf. Here are some comments 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 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.)

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.

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.

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

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..

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.).

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 http://arxiv.org/abs/0706.3565 (Thanks to Mathieu Chapelle for providing this link.).

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.

(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.)

In March 2008 SCynthia Ann Harlan Krieger, applied for a patent for a polynomial time solution for the (NP-complete) Hamiltonian circuit problem: http://www.freepatentsonline.com/y2008/0071849.html The full proofs of the underlying theorems are available in the paper "The Proof of P=NP" by Cynthia Ann Harlan Krieger and Lee K. Jones. (Thanks to Alasdair Urquhart for providing these links.)

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.

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.

In June 2008 Rafee Ebrahim Kamounaproved 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 Additional information on this approach can be found at http://kamouna.wordpress.com . (Thanks to Ronald Ortner for providing this link.)

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.).

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 .

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. 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 [pdf] (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 , 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. In 2013, an updated version of the paper was presented at the 2013 IEEExploreACIS 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 IEEExplore. (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 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. Follow-ups: The paper "Refutation of Aslam's Proof that NP = P" 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 "Response to Refutation of Aslam's Proof that NP = P". (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 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.

On the 1st of April 2009 Doron Zeilberger, 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.)

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. Further versions have been published in 2010 and 2011. More information on the current version of the proof is available at http://trytoprovenpvsp.blog.sohu.com/entry/ Since May 2013, the paper "A Polynomial Time Algorithm for the Hamilton Circuit Problem" is available at http://arxiv.org/abs/1305.5976 (Thanks to Maris Ozols for providing some of these links.)

In June 2009 Arto Annila , 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.The paper has also been published in the journal ISRN Computational Mathematics 2012 ID: 321372, 1-15, and is available at http://www.isrn.com/journals/cm/2012/321372/ (Thanks to Matti Niemenmaa for providing some of these links.).

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 . 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 http://arxiv.org/abs/1106.1150 . (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 http://arxiv.org/abs/0909.3466 . (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 http://arxiv.org/abs/0909.3868 Some additional information (and a pdf-file explaining the spirit of the proof) is available at the author's page http://www.visainformatica.it/3sat (Thanks to Dirk Gerrits for providing this link.)

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.

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.)

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.)

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.)

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 http://arxiv.org/abs/1006.2218 (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 http://arxiv.org/abs/1006.2495. 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 http://arxiv.org/abs/1009.0884 (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 http://arxiv.org/abs/1007.4257 Additional information on this approach can be found at http://mkatkov.wordpress.com (Thanks to Dirk Gerrits and Michael Thomas for providing this link.)

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. Technical 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 pdf-file Lots of useful discussions on this proof: http://rjlipton.wordpress.com/

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 313-321. And here is a refutation 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 http://arxiv.org/abs/1011.3944 Additional information can be found at http://romvf.wordpress.com/2011/01/19/open-letter/ (Thanks to Dirk Gerrits for providing this link.)

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

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 http://arxiv.org/abs/1101.0160 (Thanks to Mathieu Chapelle for providing this link.)

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 http://www.iigss.net/Scientific-Inquiry/Dec2010/table.htm (Thanks to Jeffrey Forrest for providing this link.)

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 http://arxiv.org/abs/1101.2018 (Thanks to Guillaume Aupy for providing this link.)

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 http://arxiv.org/abs/1104