W3C home > Mailing lists > Public > public-bitcoin@w3.org > October 2019

Unique Games Conjecture (Informal) Proof

From: Andrew DeSantis <desantis.bitcoin@gmail.com>
Date: Mon, 7 Oct 2019 16:39:23 -0500
Message-ID: <CAJafQZxBZ8sxPQwYmX3=Gr3EX+JJwLLodeio=V+=3admiHWA7g@mail.gmail.com>
To: public-bitcoin@w3.org
What follows is an informal proof of the "Unique Games Conjecture" made by
Subhash Khot in 2002.

"The conjecture postulates that the problem of determining the approximate
value of a certain type of game, known as a unique game, has NP-hard
algorithmic complexity. It 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.
....
In 2008, Prasad Raghavendra has shown that if the UGC is true, then for
every constraint satisfaction problem (CSP) the best approximation ratio is
given by a certain simple semidefinite programming (SDP) instance, which is
in particular polynomial." : [
https://en.m.wikipedia.org/wiki/Unique_games_conjecture]

Everything needed to write a formal proof of UGC can be found at the
following locations:
https://www.chessprogramming.org/0x88
http://www.bitsavers.org/components/intel/MCS80/MCS80_85_Users_Manual_Jan83..pdf
https://en.bitcoin.it/wiki/Mini_private_key_format
http://gobittest.appspot.com/VanityAll
https://en.m.wikipedia.org/wiki/Binary_Synchronous_Communications
https://blockchair.com/bitcoin/transaction/0617e6c51f4688dbce87e86e5cb8e7e800b1276ce7425d0f193ee0e044fe369d
https://blockchair.com/bitcoin-sv/transaction/dd727e4541b812b7fb34d76db020f2440efe240beb791b3f7f146eb72341ce1c
https://blockchair.com/bitcoin/transaction/266b6dc76f2802595409de58417ef83e591e12a59e6d6d6c53437887aa5995d3
https://blockchair.com/bitcoin/transaction/e5fc2a75f15fa2df4f1eeea56f43d90bff9679184b39c8827a97cbbc35f19db2
https://blockchair.com/bitcoin/transaction/36f63b0cdb81a5f8e428b459f92712408168c4b28089cf12a18fac874fe1d85d
https://blockchair.com/bitcoin/transaction/d6b58d73759ce7b3678dd6c960f8fd4a0eb4eb3cc1edadb787e4aa63d7fdf78b
https://blockchair.com/bitcoin-sv/transaction/30acfe2e782626671dea428c2f0b37ccc099c0e2551876e3593c782426f2ccbf
https://blockchair.com/bitcoin-sv/transaction/67e893df945fbea1a980bbe17c8ae49e27839c060f5b899513e5c419f52b3eb6
https://blockchair.com/bitcoin/transaction/f377f3db3535cf385fd2c63e7d30f67b3f955df19e15c61dc817425663e3936b
[image:
fe6b37526789d80329a37399a15be74e22e1d31da8527babe6fbfaabdcb0c663.jpeg]
^
https://whatsonchain.com/tx/fe6b37526789d80329a37399a15be74e22e1d31da8527babe6fbfaabdcb0c663
[image:
6b81c18757004aa86a0fb8fa3171a7d4a3d33fa7d3aafafd2a84a4c539b325a9.jpg]
^
https://whatsonchain.com/tx/6b81c18757004aa86a0fb8fa3171a7d4a3d33fa7d3aafafd2a84a4c539b325a9
[image:
b43cd98fd05f8eed44797d49270a58fe5c7b7e9c36b26cdfa39bda114690a109.jpg]
^
https://whatsonchain.com/tx/b43cd98fd05f8eed44797d49270a58fe5c7b7e9c36b26cdfa39bda114690a109
[image:
457937c769b6bba67ef27f2c07917faccb6d86a08a7fb189debf43864deb81d7.jpg]
^
https://whatsonchain.com/tx/457937c769b6bba67ef27f2c07917faccb6d86a08a7fb189debf43864deb81d7
[image:
8d3cb306922092d16f3ac9c4e1f026cadd148b025bd72e9d6b9313c62ee41af8.jpg]
^
https://whatsonchain.com/tx/8d3cb306922092d16f3ac9c4e1f026cadd148b025bd72e9d6b9313c62ee41af8

I am currently focused on my browser, becoming a father (again) and
starting an electric company (meaning "I am not an academic"). I am posting
the primitives of the UGC proof informally in the hopes that they might be
useful to you in the event that I never complete a formal proof (as I am
the type of person who would write said proof in German in the spirit
of "Über formal unentscheidbare Sätze der Principia Mathematica und
verwandter Systeme I" just b/c... again "I am not an academic").

~a

fe6b37526789d80329a37399a15be74e22e1d31da8527babe6fbfaabdcb0c663.jpeg
(image/jpeg attachment: fe6b37526789d80329a37399a15be74e22e1d31da8527babe6fbfaabdcb0c663.jpeg)

6b81c18757004aa86a0fb8fa3171a7d4a3d33fa7d3aafafd2a84a4c539b325a9.jpg
(image/jpeg attachment: 6b81c18757004aa86a0fb8fa3171a7d4a3d33fa7d3aafafd2a84a4c539b325a9.jpg)

b43cd98fd05f8eed44797d49270a58fe5c7b7e9c36b26cdfa39bda114690a109.jpg
(image/jpeg attachment: b43cd98fd05f8eed44797d49270a58fe5c7b7e9c36b26cdfa39bda114690a109.jpg)

457937c769b6bba67ef27f2c07917faccb6d86a08a7fb189debf43864deb81d7.jpg
(image/jpeg attachment: 457937c769b6bba67ef27f2c07917faccb6d86a08a7fb189debf43864deb81d7.jpg)

8d3cb306922092d16f3ac9c4e1f026cadd148b025bd72e9d6b9313c62ee41af8.jpg
(image/jpeg attachment: 8d3cb306922092d16f3ac9c4e1f026cadd148b025bd72e9d6b9313c62ee41af8.jpg)

Received on Monday, 7 October 2019 21:41:23 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:08:12 UTC