What to do if you have a proposed solution to P vs NP?

Do you have a proposed P vs NP solution? Did someone send you a proposed P vs NP solution and ask you to review it?

This repository was setup to help people who believe that they solved the P vs NP problem and to help the people who review proposed solutions.

P vs NP is a popular problem that has captured a lot of people's interests.

P vs NP is an elusive problem at the intersection of mathematics and computer science. If you're not already familiar with this problem, then there are plenty of helpful resources available online. A quick web search will return results with headlines such as "Explained: P vs. NP", "What is the P vs. NP problem and why is it so important?", and "The Practical Implication of P vs NP Problem".

Cut to the chase: The P vs NP problem has attracted a lot of attention. Some suspect that a solution to this problem could be of great practical significance and some think that solving P vs NP could bring fame and fortune with the promise of a million dollar prize.

Professional & amateur researchers continue to submit proposed solutions.

• There is an extensive list of articles, papers, and write-ups containing proposed P vs NP solutions.

• Proposed solutions will from time to time appear on arXiv and other platforms for archiving & publishing.

• Proposed solutions have been submitted on Stack Exchange and even in the comments on complexity theory blogs.

• Proposed solutions have been cold emailed to researchers and are sometimes submitted to journals / conferences.

• I personally have had at least three different people send me their proposed P vs NP solutions.

What to do if you have a proposed solution?

• Take a step back and try to understand what you are doing so that you will be prepared to best explain your approach to others.

• Start with the small results. I believe that any substantial proof should be broken up into smaller pieces that are easier to digest. If you have a collection of smaller results, you might be able to first publish a paper just on these smaller results. If your approach has value, then people will ask questions that you haven't considered and these questions could lead you to many more small results and more papers.

• Your proof technique should mean something to you. It's not merely a vehicle to resolve the P vs NP problem. It should have some reasoning behind it.

• Be open minded. Be conscious of the possibility that you made a mistake and also that others make mistakes. In particular, there are plenty of mistakes in published academic papers.

• Know your niche. I generally believe that it's easier to get helpful and thoughtful advice from people within your niche. For example, if your proposed solution involves vertex cover, then know everything that there is to know about vertex cover. Talk to people who work on vertex cover and continue working on other problems related to vertex cover. Recognize that it might be difficult for someone to review your paper if they don't have extensive knowledge of the vertex cover problem.

My personal experience with proposed P vs NP solutions

• I personally have reviewed at least three proposed P vs NP solutions. Here are some of my insights for anyone who plans to review a proposed solution:

  • Direct communication is important because it's easy to get stuck when trying to understand someone else's proof.
  • Failed proofs can lead to interesting results. Even when there is a bug in a proof, there can be interesting lemmas and small results that should be pursued further. It was saddening in a few cases where the submitter had little interest in further pursuing such results that I believe could have potentially been published.
  • Reviewing can be strenuous and difficult. It can be challenging to understand someone else's ideas, especially if their approach is totally new or if it is lacking in presentation because details are missing and proofs are not broken up into smaller more digestible pieces.

• I have proposed solutions to open problems in complexity theory. Many of my proposed solutions turn out to be false. But, in some cases one or more of the following applied:

  • They still led to interesting insights and important smaller results.
  • They led to interesting discussions and new collaborations.
  • They required a lot of effort before coming to a clear resolution.

What content can we provide that might be helpful?

• Thoughts, Ideas, and Advice for researchers and reviewers.

• Although I can only review one or two proposed solutions per year, I would be happy to be a volunteer reviewer for your proposed P vs NP solution. Please contact me @ [email protected]. Also, you are welcome to list links to any of your publicly available proposed solutions within our Proposed-solutions.md document.

• Would anyone else out there like to be a reviewer for proposed P vs NP solutions?

• Please suggest other things that we can do to help!