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

111–120 of 303 posts

Re: A Solution of the P versus NP Problem?

#111

Post by westoncb »

kittysasa wrote: post #84
wolfgke wrote: post #76

Earlier quoted context omitted.

After overlooking the paper and applying Scott Aaronson's criterion I bet against you and bet: - The proof will turn out to have a flaw - The flaw will not be that hard to find (though probably not completely trivial; but rather of the kind: it takes much time to go to the details of the proof arguments) - The flaw will not be interesting in itself and will not advance the field

Seconded. The flaws in these papers are not hard to find. They usually amount to misunderstanding of definitions or the results they cite.

Unlikely considering the author of the paper. I'm basing that on other comments on the thread which this section seems to be missing, e.g.:

> ...this guy is an established senior researcher at the University of Bonn

Re: A Solution of the P versus NP Problem?

#113

Post by mihaild »

vanjoe wrote: post #56
zolthrowaway wrote: post #21

Earlier quoted context omitted.

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

There is Universal Search algorithm. If P=NP, it finds a solution for solvable 3-SAT in polynomial time. (still not solving 3-SAT itself in case we will not be able to determine running time, but in cryptography AFAIK we usually need solutions for known-solvable instances)

Re: A Solution of the P versus NP Problem?

#114

Post by zmonx »

hexomancer wrote: post #109
mihaild wrote: post #108

Earlier quoted context omitted.

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.

You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral).

Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.

Re: A Solution of the P versus NP Problem?

#115

Post by Sharlin »

vanjoe wrote: post #56
zolthrowaway wrote: post #21

Earlier quoted context omitted.

The most interesting thing is if P=NP. If that's the case, that means that there is an algorithm that can solve any NP problem in polynomial time. This means that things like crypto would be able to be cracked in polynomial time which presents a huge problem for security. We basically operate under the assumption that P!=NP currently. Validation that this is true doesn't really change much. I can't speak to how this…

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

Re: A Solution of the P versus NP Problem?

#116

Post by nieve »

WhitneyLand wrote: post #72
jjgreen wrote: post #2

I would normally sigh and move on seeing such a claim, but this guy is an established senior researcher at the University of Bonn. A career-ending disaster or instant and eternal fame, that's some serious cahunas.

It shouldn't be career ending unless there's been malfeasance or some kind of sloppy work. The people who go down hard usually have some crime beyond audacity. It could easily cause some painful embarrassment, but hopefully that would pass with time. Maybe embarrassment similar to that faced by researchers who's results suggested FTL communication, but it turned out to be a bad fiber-optic cable. I didn't follow up b…

I wouldn't be surprised if they gained a bit of respect. If I recall correctly they did everything right - they had an apparently impossible result, they spent a lot of time trying to disprove it, and when they announced they made it clear that they doubted the result. Hiding it because they were sure it was false, but couldn't disprove would have been poor science. It had to be pretty scary to make that announcement knowing there was almost no chance it wasn't going to turn out to be a problem in their setup and I admire the guts it took to do it.

Sometimes the courage of your convictions means trusting the process to get it right when you're sure you're wrong.

Re: A Solution of the P versus NP Problem?

#117

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…

Epsilon isn't a problem, as TSP is NP-complete even for integer weights. Your solution needs some modification for case where we have multiple optimal cycles (as you will find edges that are included in at least one cycle).

I don't think there is anything wrong with optimization been reducible to decision - it's quite common method both in theory and in practice.

Re: A Solution of the P versus NP Problem?

#119

Post by anarazel »

Sharlin wrote: post #115
vanjoe wrote: post #56

Earlier quoted context omitted.

I think it's even less useful, even if P = NP it is possible that no one finds an algorithm. Creating a (useful) algorithm is independent of proving the theorem. Also interesting is that someone could create an algorithm that solves NP complete in polynomial time without proving P=NP. They would be unable to prove the algorithm correct though.

If P=NP, then finding an algorithm is, by certain definition, exactly as easy as proving an algorithm correct! This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

> This is, after all, the gist of what P vs NP means. And this is why it's such a huge deal - the problem is almost self-referential in nature.

Could you back that up with some citations? This doesn't ring true. But my pure CS has withered a bit...

Re: A Solution of the P versus NP Problem?

#120

Post by contradictioned »

teton_ferb wrote: post #33
RSchaeffer wrote: post #6

Can someone ELI5 what this problem is, how likely the proof is to hold up to scrutiny, and whether P != NP follows?

Here is a largely correct ELI5: P != NP asks the question "Are problems that are easy to verify (NP) also Easy to solve ? (P)". Note that the reverse is obviously true : problems that are easy to solve are also easy to verify . Here is an example: Take the problem "Find minimum of 5,6,7,8". You solve the problem and tell me that the answer is 5. I can verify your answer by solving the problem myself, getting the the…

I want to add another important aspect, the aspect of NP completeness. There is a bunch of problems considered "NP complete" and they are all related such that it is easy to translate one problem into another (easy as in "quickly").

This means, first: If P == NP, then all of these problems become easy, and second: if P == NP and we find an algorithm that solves only one of the NP complete problems quickly, then this algorithm can solve all algorithms quickly.

Reversely, if now this paper's proof is correct so P != NP, then there is no algorithm that solves any of these problems quickly.

Post reply on HN