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?
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.
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.
* yes i am aware that this falls apart if there is a very high constant or the algo is n^1000.
> 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?
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.
Ease of implementation could definitely be an issue.
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.