Bagaimana SETH versi MA terbukti salah?

Menurut makalah ini , yang membahas perpanjangan nondeterministik dari Strong Exponential Time Hypothesis (SETH), "[...] Williams baru-baru ini menunjukkan hipotesis terkait tentang kompleksitas Merlin-Arthur dari k-TAUT adalah salah". Namun, makalah itu hanya mengutip komunikasi pribadi.

Bagaimana SETH versi MA terbukti salah?

Saya menduga itu melibatkan algebrizing formula, tetapi tidak punya ide lebih lanjut.

Anda dapat menemukan pracetak dengan mengikuti tautan ini http://eccc.hpi-web.de/report/2016/002/

EDIT (1/24) Atas permintaan, berikut ini ringkasan singkat, diambil dari makalah itu sendiri, tetapi mengabaikan banyak hal. Misalkan Merlin dapat membuktikan Arthur bahwa untuk -variable aritmatika sirkuit C , nilainya pada semua poin di { 0 , 1 } k adalah tabel tertentu 2 k elemen lapangan, dalam waktu sekitar ( s + 2 k ) ⋅ d , di mana s adalah ukuran C dan d adalah derajat polinomial yang dihitung oleh $k$$C$$\{0,1\}^k$$2^k$$(s + 2^k) \cdot d$$s$$C$$d$$C$. (Kami menyebutnya "bukti evaluasi batch singkat non-interaktif" --- mengevaluasi pada banyak tugas.)$C$

Maka Merlin dapat memecahkan SAT untuk Arthur sebagai berikut. Diberikan CNF F pada n variabel dan klausa m , Merlin dan Arthur pertama-tama membangun sirkuit aritmatika C pada n / 2 variabel derajat paling banyak m n , ukuran sekitar m n ⋅ 2 n / 2 , yang mengambil jumlah atas semua penugasan ke variabel n / 2 pertama dari CNF F (menambahkan 1 ke jumlah ketika F benar, dan $\#$$F$$n$$m$$C$$n/2$$mn$$mn \cdot 2^{n/2}$$n/2$$F$$1$$F$$0$ketika itu salah). Dengan menggunakan protokol evaluasi batch, Merlin kemudian dapat membuktikan bahwa mengambil 2 n / 2 nilai tertentu pada semua penugasan Boolean 2 n / 2 , dalam waktu sekitar 2 n / 2 p o l y ( n , m ) . Menjumlahkan semua nilai-nilai tersebut, kita mendapatkan hitungan tugas SAT untuk F .$C$$2^{n/2}$$2^{n/2}$$2^{n/2} poly(n,m)$$F$

Sekarang kita katakan pada tingkat tinggi bagaimana melakukan protokol evaluasi batch. Kami ingin bukti untuk menjadi representasi ringkas dari sirkuit yang baik mudah untuk mengevaluasi pada semua 2 k diberikan masukan, dan juga mudah untuk memverifikasi dengan keacakan. Kami menetapkan bukti menjadi polinomial Q ( x ) univariat yang didefinisikan pada bidang ekstensi yang cukup besar dari bidang dasar K (dengan karakteristik minimal 2 n untuk aplikasi kami), di mana Q ( x ) memiliki derajat sekitar 2 k ⋅ d , dan Q `sketsa '' evaluasi gelar-$C$$2^k$$Q(x)$$K$$2^n$$Q(x)$$2^k \cdot d$$Q$ sirkuit aritmatika$d$ atas semuapenugasan 2 k . Q polinommemenuhi dua kondisi yang saling bertentangan:$C$$2^k$$Q$

• Verifier dapat menggunakan sketsa untuk menghasilkan tabel kebenaran C secara efisien . Secara khusus, untuk beberapa α i yang diketahui secara eksplisit dari ekstensi K , kita ingin ( Q ( α 0 ) , Q ( α 1 ) , … , Q ( α K ) ) = ( C ( a 1 ) , … , C ( a 2 K ) ) , di mana $Q$$C$$\alpha_i$$K$$(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$$a_i$$i$$k$$C$

• $Q$$C$$2^k$$2^k + s$

$Q$