> 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.
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.
We employ the minimum_edge_cut() function from NetworkX to identify the minimum edge cut within an undirected graph. By iteratively solving the minimum edge cut problem on the connected components of the graph, we can obtain an approximate solution to the Minimum Vertex Cover Problem with an approximation ratio less than sqrt(2).
> 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.
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.
It's from the same author that recently made "a breakthrough" triangle counting algorithm and has "strong evidence for P=NP".
We employ the minimum_edge_cut() function from NetworkX to identify the minimum edge cut within an undirected graph. By iteratively solving the minimum edge cut problem on the connected components of the graph, we can obtain an approximate solution to the Minimum Vertex Cover Problem with an approximation ratio less than sqrt(2).