Thank God! The Unique Games Conjecture has been Disproved!!! [By us]

Aditya Yadav
Nov 26, 2019 · 5 min read

What is the Unique Games Conjecture?

Many important optimization problems are NP-hard to solve exactly in the worst case. When faced with such a problem, we have to settle for an approximate solution. An approximation algorithm for an NP-Hard problem is a Turing Machine that produces a feasible solution to the given problem that is within a guaranteed factor of the optimum solution. Usually, this factor is taken to be greater than 1, so for a maximization problem, an approximation algorithm that achieves a factor C produces a solution whose value is at least OPT/C, where OPT refers to the problem’s global optimum solution. For a minimization problem, a factor C approximation algorithm produces a solution whose value is at most C*OPT.

Finding an approximation algorithm is one aspect of studying the approximability of an NP-hard problem. The other aspect is proving, under certain assumptions, that the problem cannot be approximated within a certain factor. Such results that rule out the possibility of an approximation algorithm are referred to as hardness results or inapproximability results. Usually, they are based on the assumption that P!=NP, thus ruling out the possibility of a polynomial time approximation algorithm.

Early inapproximability results are due to Garey and Johnson. However, strong inapproximability results for many problems were not obtained until the connection between approximation hardness and multiprover interactive proofs was discovered by Feige et al.. An interactive proof can be viewed as a game between a computationally unbounded prover, and a polynomial time algorithm called the verifier with access to random bits. The prover wants to convince the verifier of some fact, e.g. that a given string is in a language, and the verifier (probabilistically) decides whether to accept the fact or not by querying the prover.

The Unique Games conjecture is about a certain type of interactive proof with 2 provers. It implies strong inapproximability results showing for example that unless P = NP, Min-2SAT-deletion cannot be approximated within any constant factor, and that under the same assumption vertex cover in k-uniform hypergraphs cannot be approximated within a factor of k − ε for every k ≥ 2 and ε > 0. In particular, this means that the conjecture would settle the vertex cover problem on graphs since there exists a factor 2 approximation algorithm for this problem. The conjecture would also settle the Max-Cut problem as it would imply that the approximation factor achieved by the algorithm of Goemans and Williamson is the best possible.

Wow! That was intense. What does all this mean? What does all this imply?

Unique Games Conjecture has broad applications in the theory of hardness of approximation.

If it is true, then for many important problems it is not only impossible to get an exact solution in polynomial time (as postulated by the P versus NP problem), but also impossible to get a good polynomial-time approximation.

The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.

Where can I learn more about Unique Games Conjecture?

How can we disprove the Unique Games Conjecture?

Given an NP-Hard problem…

we can either find the perfect solution in polynomial time

or

we can find an approximation algorithm, which works in polynomial time, to the extent of a perfect solution

or

in some specific cases finding an polynomial time approximation algorithm, which by itself will disprove the Unique Games Conjecture

Simble!

And by doing the above we will also prove that P = NP! Yay!

And what are some such NP-Hard Problems?

Constraint Satisfaction Problem(s)

QUBO — Quantum unconstrained binary optimization

QAOA — Quantum approximate optimization algorithm

Max-Clique

TSP — Travelling Salesman Problem

Max — E3Lin2

Please see…

And now we have successfully approximated in polynomial time, to the degree of a perfect solution, the K-CSP & K-CSO Problem.

Conclusion

Not only does this destroy the Unique Games Conjecture. It also proves P = NP for the 2 dozen’th time since 1990's.

Because most of these problems were considered unapproximable to ‘any’ degree.

And while we have approximated them in polynomial time. Destroying the Unique Games Conjecture.

We have also approximated them to an arbitrary degree, to the extent of a perfect solution. All in polynomial time. Which also proves P = NP.

Not only has the polynomial hierarchy and complexity tree fallen. We are now just on the verge of conquering the final frontier, that of EXP-Complete and EXP-Hard problems. As of today we can solve some of them in polynomial time. But what we are really looking for is a class of algorithms to vanquish the entire space.

Needless to say, this means a phenomenal amount of success, prosperity, health, progress for mankind.

We have defined the next millennium of mankind.

Time to light a cigar…

About us

This is our website http://automatski.com

NirvanaThroughKarma

The transcendent state in which there is neither suffering, desire, nor sense of self, and the subject is released from the effects of karma and the cycle of death and rebirth.

Aditya Yadav

Written by

Millennium Inventor

NirvanaThroughKarma

The transcendent state in which there is neither suffering, desire, nor sense of self, and the subject is released from the effects of karma and the cycle of death and rebirth.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade