3 ms·
So just from the headline, "unknown person solves p=np" there is a 99.9999% chance this is wrong. However if i read the first sentence of the abstract correctl
by bawolff 4y ago
So just from the headline, "unknown person solves p=np" there is a 99.9999% chance this is wrong.
However if i read the first sentence of the abstract correctly, they are claiming to have a constructive proof (i.e. they found an algorith). So can't we just check the proof by using their alleged algorithm on some np-hard problems?
- paulpauper 4y agono. they may still be impractically unsolvable
- Reventlov 4y agoYeah, P=NP says nothing about the possibly enormous constant factor in front of your poly-time algorithm.
- bodhiandpysics1 4y agoNp hard problems aren't that hard to solve. I'm solving one right now actually for work (graph bi-partition using simulated annealing), and it doesn't even take that long. Of course my algorithm isn't actually correct! Or if I had a correct algorithm it might be really fast but still not have polynomial growth. You need a proof.
- bawolff 4y agoYou need the proof to show it really works in all cases. However if the goal is some quick (non-exhaustive) verification, then why can't you just use the algorithm? (Ignoring the big constants, high degree polynomial issue siblings mention). Either A, it doesn't work, showing the paper is incorrect. Or B it works, showing that even if it doesn't prove the paper fully correct, it shows that at least something interesting is going on.
- bodhiandphysics 4y agoThis algorithm solves all np problems. For all possible solutions (there are at most 2^p(x) where p is some polynomial), Check if that solution is correct. This of course takes exponential time. Just because you have an algorithm to solve np problems doesn’t mean you’ve done something useful.
- bawolff 4y agoI mean use it on an instance of the problem big enough that an exponential algorithm would take years and see if the new algorithm doesn't *. Either something interesting will happen or it won't. * yes i am aware that this falls apart if there is a very high constant or the algo is n^1000.
- glitchc 4y agoThis belies a misunderstanding of NP space. Any problem is easy to solve if the dataset being processed is small enough. Computers are wonderful at brute-forcing terrible solutions.
- coliveira 4y ago> can't we just check the proof by using their alleged algorithm on some np-hard problems? Not necessarily. An algorithm may be polynomial but impractical for all but the most trivial cases. Moreover the algorithm may be very difficult to implement correctly.
- nestorD 4y agoThe large constant problem might not apply here as NP problems suffer from an exploding complexity: you don't need to grow them that much to reach a point where that constant would be a non-issue. Ease of implementation could definitely be an issue.
- not2b 4y agoYou can't check the proof by "using their alleged algorithm on some np-hard problems". You would have to prove that all problems in the space are handled in polynomial time by their algorithm, correctly. In electronic design automation we have to deal with NP-hard problems all the time. One approach is to use algorithms that are worst-case exponential but that finish quickly most of the time even for fairly sizable problems, or that fail to provide a solution for some cases. SAT solvers are a typical example. Another, for an optimization problem, is to provide a good solution that is not necessarily optimal.
- espadrine 4y agoTheir claim is: > Conjecture. There is no polynomial time algorithm for deciding <some problem>. […] [A variant of the problem] is NP-complete. […] Theorem 2. There is a constructive algorithm for deciding [the variant problem]. The number of basic steps to do this [is bounded by something that is, I think, intended to be polynomial, although there is a hidden exponent of k and a direct exponent of n]. I don’t see any justification or source for the statement that the variant problem is actually NP-complete. Even if their proof was correct, wouldn’t it just disprove a conjecture?