A polynomial algorithm for the maximum clique.
Ioannis Avramopoulos · arXiv (Cornell University) · 2020
In this paper, we present a polynomial-time algorithm for the maximum clique problem, which implies P = NP. Our algorithm works with a continuous representation of this problem that is parametrized and uses an computation engine that, depending on the value of the parameter, either detects a maximum-clique equilibrium or decides that such an does not exist (for that parameter). From a technical perspective, one of our contributions is to transform an fully polynomial-time approximation scheme to a polynomial-time computation algorithm for the continuous representation we are working with.