3 ms·
How the world will be if P = NP?
The P versus NP problem is of theoretical and practical importance in computer science. The question is whether finding a solution to a problem is easy as checking a proposed solution for correctness. If any NP complete problem is in P, then P and NP are the same class of problems.
I found a polynomial time algorithm for the traveling salesman problem (TSP) with distances a and b. This special case of the TSP is NP complete. The algorithm finds an optimal tour in time at most proportional to n^2 and it's much more efficient for finding a tour of a graph (Hamilton cycle). I post on my resolution of P vs NP at https://www.pvsnp.blog
Good and bad consequences will result if the equality is true. What do you think is the most positive about P = NP?
- verdverm 9mo agoIf you've actually proved it, submit it to peer review instead of HN I doubt you have resolved it or need to answer your orig question
- fouadelkh 9mo agoThere is no need to submit it to peer review.
- deleted 9mo ago[deleted]
- gus_massa 9mo agoThe specific case looks interesting. (I didn't read it yet.) Anyway, the title will make people ignore the blog because there are too many false claims about P=/!=NP that is boring t read them. My suggestion is to repost this with a very specific title "Solving the TSP in the special case when there are only two distances" or something like that. Anyway, I get a 404 in https://www.pvsnp.blog/ https://www.pvsnp.blog/
- jfengel 9mo agoThe consequences are pretty severe. It's considered wildly unlikely that P=NP. It's like being told that sometimes 2+2 really does equal 5. Effectively everybody thinks about computation gets shot. The fact of proving P=NP is less consequential than how it comes about. What oddity has been overlooked after all this time, with such counter-intuitive results? That is the part that has the consequences. There have been so many incorrect proposed proofs that it is wildly, insanely unlikely that yours is correct.
- fouadelkh 9mo agoMany more good consequences than bad consequences will result. You can't say much about the intrinsic complexity of a difficult problem. A new point of view may lead to insight into the complexity of the problem.