You 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 pol

You 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.