211–220 of 303 posts
If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.
P != NP is natural, you just gotta roll with it.
Earlier quoted context omitted.
The paper looks like it is 38 pages and builds on other work. That doesn't seem too simple to me.
I tend to agree with GP that this is suspiciously simple. I've only skimmed it, but the novel part of the proof appears to only be Thm 5-6 which is less than 10 pages, and it's not especially dense writing. So this would be a relatively simple proof. Moreover, the technique used appears to be rather incremental over known techniques, so it's surprising it would be strong enough to prove PvNP which is so far away from…
Earlier quoted context omitted.
Well yes! Two things: You have a successful algorithm that runs in P time that solves an NP Hard problem and 2) you can map other NP Hard problems to your problem. Without the second factor, it is only a demonstration of a "range" in the computational realm in question, where p = np or whatever the declaration. Being able to show that your pizza slice is actually an ocean of pizza, and also show that any other shape…
Your 2 is the easy part: "NP-hard" is exactly the set of problems to which any NP problems can be reduced in polynomial time, and there are many known existing examples, both within NP (aka NP-complete) and outside it.
I like the straightforward title. I know that it is politically correct to christen your paper solving e.g. the Poincare conjecture like e.g. "Ricci flow with surgery on three-manifolds", but all rules are there to be broken once. I wish the author best of luck.
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…
Earlier quoted context omitted.
Your 2 is the easy part: "NP-hard" is exactly the set of problems to which any NP problems can be reduced in polynomial time, and there are many known existing examples, both within NP (aka NP-complete) and outside it.
So part of the solution set satisfies P=NP and some satisfy P!=NP?
So at least according to this P != NP. I’ve always been skeptical of this just because if you find an efficient optimal algorithm the problem moves between the classes.
This hasn't ever happened.
You can prove an algorithm is in NP-hard by reducing another NP-hard problem to it. You can prove an algorithm is in P by showing the algorithm.
If you find and efficient algorithm to a problem in NP-hard, you show P == NP. No one has ever done this.
P != NP is considered by many to be most likely true.
Earlier quoted context omitted.
After skimming its interesting that the majority of the proofs in your list claim P equals NP. I would have guessed it would be more common for proofs to claim the opposite because P != NP makes sense intuitively. That being said it would certainly be more exciting if P did equal NP.
A simple but wrong proof of "P = NP" is easier to write in some ways, since you "just" need to provide a single algorithm for one NP-hard problem, and show that it runs in polynomial time. It looks like many or most of the proof attempts in that list take this form. A plausible proof of "P != NP" won't be quite as simple to express, since it needs to prove that all such algorithms do not run in polynomial time.
That sounds hard but, If for any NP-Complete problem there exists no P solution then for all NP problems there is no P solution. So this proof sounds like it has the right shape.
If p != np, then comp sci will lose much of its appeal. There is an underlying hope behind the field that p = np, otherwise most problems of interest are intractable, and programmers are no longer masters of the universe. This is probably why there is not a proof yet, since the truth is undesirable.
I'm not sure what you mean by "appeal." But, it seems to me that if P = NP, and if we can find a constructive proof of this fact, i.e. someone presents a P-time algorithm A_L deciding an NP-complete language L, the field of CS in a sense would get much less interesting, because although we would have answered arguably the most important question ever posed, there would be much less of a need to research and develop e…
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