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

121–130 of 303 posts

Re: A Solution of the P versus NP Problem?

#121

Post by hexomancer »

mihaild wrote: post #117
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…

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.

I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry...

note: I am not implying that the above source is reputable. But it does hint that the solution to this problem probably is not this trivial.

Re: A Solution of the P versus NP Problem?

#122

Post by lorenzhs »

kevinwang wrote: post #112
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.

What's a good explanation of that?

2SAT is boring because given a clause with one unfulfilled literal, you know the other literal must be satisfied. There's no choice to be made. This limits backtracking enormously. It can even be solved in linear time (although that's nontrivial)

Re: A Solution of the P versus NP Problem?

#123

Post by acchow »

adrianmonk wrote: post #42
js8 wrote: post #3

Earlier quoted context omitted.

> A career-ending disaster Why? Why should posting a stab at a complicated problem should be considered career-killing?

Some people will hold it against him because some people are too stupid to see things in context. Rather than respecting him for taking a smart risk in pursuit of an important goal, they will just remember that he was once wrong about something and in a big way. There are people who point at others' failures to bolster their own image by comparison. And there are people with fragile egos who are eager to see others i…

Is this really how the academic community is?

Re: A Solution of the P versus NP Problem?

#124

Post by 1ris »

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

Proof for the Gaussian correlation inequality was

- Written in Word

- Uses techniques just seem too wimpy for the problem at hand.

- Was published in a predatory journal

Re: A Solution of the P versus NP Problem?

#125

Post by brianberns »

TekMol wrote: post #75

Say you wanted to let a computer search for a proof of P!=NP - which axioms would you start with and which rules to transform the axioms into additional valid statements?

I wonder if the algorithm to search such a space of axioms and transforms for a solution would itself be P or NP. :)

Re: A Solution of the P versus NP Problem?

#126

Post by zmonx »

phkahler wrote: post #80
DonbunEf7 wrote: post #63

Earlier quoted context omitted.

To follow up on this, in computational linguistics, there is a sharp divide between facts which take cubic time, like recognizing whether a string belongs to a context-free language, and facts which are halting-problem-hard, like recognizing whether two context-free grammars describe the same language. There doesn't appear to be much of a middle ground. In another realm of computational mathematics, matrix mjultiplic…

The AKS algorithm has been reduced to an exponent of 6. That really strikes me as large for polynomial time algorithms though.

It is! At first, the following may appear quite counter-intuitive, but if you think about larger N and the fact that you often want efficient algorithms also when processing large amounts of data, it becomes clear that an exponent of 2 or 3 is, in practice, often the most we can realistically handle even when the problem is in P, and even though O(n^2) is extremely low from a computational complexity perspective.

For example, when you have an O(n^3) algorithm and want to process 10,000 elements (which are very few in many situations), it will be, as a rough estimate, 1,000,000,000,000 times slower than processing a single element. This will be acceptable only in very specific situations. As a rule of thumb, an exponent of 2 is already unacceptably slow in many practical situations, and at least on the verge of being unacceptable in others.

Re: A Solution of the P versus NP Problem?

#127

Post by mihaild »

hexomancer wrote: post #121
mihaild wrote: post #117

Earlier quoted context omitted.

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.

I didn't say there is anything wrong with reducing the optimization to decision in general. But I feel this specific application to the TSP problem may be flawed. (for the reasons i mentioned before. i.e wikipedia being very specific about the decision version) For another resource see: https://www.ibm.com/developerworks/community/blogs/jfp/entry... note: I am not implying that the above source is reputable. But it d…

Decision version of TSP is NP-complete. Optimization version is Cook-reducible to decision version of TSP. And it problem is Cook-reducible to P-problem, then the problem is itself in P. (note that it's not true if you replace P with NP, for example)

Re: A Solution of the P versus NP Problem?

#128

Post by amelius »

mcguire wrote: post #78
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

" Yet here’s the bloodied patient, and here we are in the emergency room. " " The lemma encrusted shoulders of giants. " Aaronson on writes very well.

I'd rather he applied his test to a bunch of papers for validation and showed us a confusion matrix.

Re: A Solution of the P versus NP Problem?

#129

Post by mihaild »

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.

For example, algorithm that just copies it's input to output, unless input is proof of inconsistency of arithmetic, is correct algorithm to calculate function f(x) = x - yet it's unprovable in PA that it's correct.

Re: A Solution of the P versus NP Problem?

#130

Post by __jal »

acchow wrote: post #123
adrianmonk wrote: post #42

Earlier quoted context omitted.

Some people will hold it against him because some people are too stupid to see things in context. Rather than respecting him for taking a smart risk in pursuit of an important goal, they will just remember that he was once wrong about something and in a big way. There are people who point at others' failures to bolster their own image by comparison. And there are people with fragile egos who are eager to see others i…

Is this really how the academic community is?

That's really how humanity is.
Post reply on HN