61–70 of 303 posts
This is definitely one of those "I'm going to wait for the peer review" claims, but it is pretty exciting. Pros: The author is not a dilettante, and is actively researching in the area ( http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var ) Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...). Could be pr…
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.
Earlier quoted context omitted.
This interpretation is wrong. The class P contains for example O(N^(10^100000!)), that are not "solvable" by any remotely reasonable meaning of the word.
This is true, but it's difficult to imagine what such a problem could look like. In reality, algorithms tend to come in discrete complexity "units" with very small terms. A linear algorithm isn't just fast -- it tells you something about how such an algorithm works and thus something important about the problem it solves. A quadratic algorithm can be interpreted as a "considers all pairs from the inputs" algorithm. A…
In another realm of computational mathematics, matrix mjultiplication is cubic, with optimizations that can approach quadratic time with lots of effort. It's conjectured that matrix multiplication can actually be brought arbitrarily close to quadratic time, but at the expense of ever-more-complex algorithms.
It could very well be that the biggest interesting exponent in P is 3 or 4.
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.
On your second point, a construction which transforms NP-complete problems into P problems in polynomial time necessarily implies P = NP, by construction. If the algorithm isn't correct, then it's a heuristic, not an algorithm, and we have piles of heuristics for working with NP-complete problems already.
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.
Think about non-constructive proofs.
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.
Is that really true though? What if someone solves does P equal NP problem by finding a polynomial time algorithm for a problem in NP, but the asymptotic run time is O(n^10^100)? Sure the race would be on to improve that, but in the meanwhile no difficult problems would become solvable.
It's easier to get people to devote resources to a hard but solvable problem than to one which may not even be solvable.
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.
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
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.
> A career-ending disaster Why? Why should posting a stab at a complicated problem should be considered career-killing?
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.
I think you mean "cojones" (which btw is a very rude word in Spanish). A kahuna is a kind of Hawai'ian shaman.