Capablanca: Minimum Vertex Cover Solver

by vegafrank • 1 year ago

18 3 1 year ago

stncls• 1 year ago

Complexity
We present a polynomial-time algorithm achieving an approximation ratio below √2 for MVC, providing strong evidence that P = NP by efficiently solving a computationally hard problem with near-optimal solutions.
This result contradicts the Unique Games Conjecture, suggesting that many optimization problems may admit better solutions, revolutionizing theoretical computer science.

Some context: The Unique Games Conjecture (UGC) is a very central unsolved problem in theoretical computer science (TCS), it's open since 2002. It conjectures that, for a series of standard optimization problems including minimum vertex cover, the best known approximation factor (how close you can guarantee to get to optimality with a poly time algorithm) is actually the best possible approximation factor. To disprove the conjecture, one needs a better approximation algorithm for one of those problems. Such an algorithm could be used to solve (to optimality, and in poly time) another set of problems, which are widely believed to be NP-hard. This would not prove P=NP (to be clear: the above quote is not claiming that), but it is true it would revolutionize TCS.

The thing is: this is TCS and theoretical complexity. You cannot disprove UGC with just code. You need a mathematical proof. This is not an indictment of the code which may be very good. But such an enormous claim would require pretty intense scrutiny before it would be accepted as true.

bicsi• 1 year ago

This is just BS.

If you follow their paper, their "inductive" argument can also prove that the result is optimal (the sqrt(2) constant is taken from thin air and may also be replaced by 1 without changing the proof).

My guess is that they tested some graphs, and "empirically" saw a bound of sqrt(2), and then came up with a proof to self-fulfill the profecy. They even mention that "for very small graphs, the approximation ratio may briefly exceed sqrt(2)", which is just nuts, given that they have a formal proof that it should never happen.

In case anyone read the paper and can't figure out the mistake in the proof, they assume that OPT_T + OPT_R = OPT, which is obviously false.

adrianN• 1 year ago

It's from the same author that recently made "a breakthrough" triangle counting algorithm and has "strong evidence for P=NP".

Capablanca: Minimum Vertex Cover Solver

Related Stories