Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Solution of the P versus NP Problem?

arxiv.org

Post reply on HN
Print view View original

101–110 of 303 posts

Re: A Solution of the P versus NP Problem?

#101

Post by jl6 »

lisper wrote: post #52
Tomte wrote: post #39

Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304

FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

Re: A Solution of the P versus NP Problem?

#102

Post by [deleted] »

jl6 wrote: post #101
lisper wrote: post #52

Earlier quoted context omitted.

FWIW, my assessment is that this paper passes the Aaronson test, as well as my own personal bogometer. If I were a betting man, my money would be on "the proof will turn out to have a flaw, but it will be hard to find the flaw, and the finding of the flaw will be interesting in and of itself, and possibly even advance the field."

And even though it may be hard to find the flaw, it will be easy to verify that it is a flaw.

[deleted]

Re: A Solution of the P versus NP Problem?

#103

Post by Analemma_ »

wolfgke wrote: post #47
davewritescode wrote: post #20

Earlier quoted context omitted.

Intuitively, almost everyone assumes that P != NP but it's been incredibly difficult to prove. If P == NP were proved it would be earth shattering, because lots of difficult problems may become solvable.

> Intuitively, almost everyone assumes that P != NP Donald Knuth believes P = NP. Source: http://www.informit.com/articles/article.aspx?p=2213858&WT.m... (question 17). Also cf. https://www.quora.com/Why-does-Donald-Knuth-think-that-P-NP

But keep in mind that he (and just about everyone who believes P = NP) thinks any proof of it will be non-constructive and that we will never actually find a polynomial-time algorithm for NP problems.

Re: A Solution of the P versus NP Problem?

#104

Post by waynecochran »

21 wrote: post #65
waynecochran wrote: post #51

If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.

Why? Proving something doesn't mean we understand all implications of said proof or how to apply it to a particular situation. Think about non-constructive proofs.

It's an important special case. You need some sort of filter for all the crazy submissions of potential proofs. I am not the only one who uses this problem as the filter.

Re: A Solution of the P versus NP Problem?

#105

Post by hexomancer »

hnaccy wrote: post #92
Govindae wrote: post #44

Earlier quoted context omitted.

Well... The traveling salesman decision problem, not the general case. The problem of finding the optimum path is not in NP, if I give you a candidate solution you can't easily check if it's the global optimum. What is in NP is the decision problem, finding a path that is better than a given bound. If I hand you a candidate solution, you just have to compare the sum of the distances to the bound to check it.

If you can solve the decision TSP in polytime you can solve the optimization case in polytime.

How?

edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version.

I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed:

First we do a binary search on `L` (the length of the tour- input to the decision version) so we can find the optimal L within a factor of epsilon (maybe this epsilon is the flaw? But I don't think that is the case.) Now we pick an edge and increase its weight to infinity. Now we do the binary search again on the new graph. If the value of the optimal solution has changed it means that the edge must be in the optimal optimization solution. By doing the same process on all the edges we can find the optimal solution.

As I said there must be a flaw in the above algorithm but I can't find it.

Re: A Solution of the P versus NP Problem?

#106

Post by naturalgradient »

zeptomu wrote: post #86

If this is true (and the proof has no flaw), it would be huge and pleasant (many expect it, although there are some who think it's a problem that might be unprovable in our current logic framework). So let's see how it works out. However the author missed that there is a special case for N == 1, where actually P == NP (sorry, I could not resist).

Don't forget the case where P == 0

Re: A Solution of the P versus NP Problem?

#107

Post by Chinjut »

waynecochran wrote: post #51

If's its legit proof, they author should be able to explain why SAT2 is in P and SAT3 is NP-complete. That's my BS test.

Whether or not this proof stands, this author, a tenured professor whose professional research is in this area, seems exceedingly likely to know this very standard material.

Re: A Solution of the P versus NP Problem?

#108

Post by mihaild »

hexomancer wrote: post #105
hnaccy wrote: post #92

Earlier quoted context omitted.

If you can solve the decision TSP in polytime you can solve the optimization case in polytime.

How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: Fir…

First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.

Re: A Solution of the P versus NP Problem?

#109

Post by hexomancer »

mihaild wrote: post #108
hexomancer wrote: post #105

Earlier quoted context omitted.

How? edit: The wikipedia mentions that the TSP problem is NP-hard and explicitly says that the decision version of this problem is NP-complete. My assumption is that if the optimization version was proven to be NP-hard there would be no need to explicitly mention the decision version. I can think of a way to use the decision version to find a solution to the optimization version but i feel like it must be flawed: Fir…

First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.

Re: A Solution of the P versus NP Problem?

#110

Post by cardiac »

Every input can be written in 1s and 0s and thus can be considered a number. Every output can be considered the same. There exists a line between every two numbers. That line can be represented by a simple one step linear regression. Now, every problem and algorithm is already an arbitrarily sized subset. If moved to the smallest possible subset, with essentially just the one input and one output, P=NP.
Post reply on HN