W jaki sposób udowodniono, że MA wersji SETH jest fałszywa?

Zgodnie z tym artykułem , który omawia niedeterministyczne rozszerzenie hipotezy silnego czasu wykładniczego (SETH), „[…] Williams ostatnio wykazał, że podobne hipotezy dotyczące złożoności k-TAUT Merlina i Artura są fałszywe”. Jednak ten artykuł przytacza jedynie osobistą korespondencję.

Podejrzewam, że wiąże się to z algebriacją formuły, ale nie mam dalszych pomysłów.

sat proofs nondeterminism

— argentpepper
źródło

Czy możesz wysłać dokument, jeśli otrzymasz odpowiedź?

Wkrótce papier. Dziękuję za cierpliwość.

— Ryan Williams,

Właściwie muszę powiedzieć, że to, co udowodnić jest znacznie silniejsza niż: „jest

Time Protocol Merlin-Arthur dla odparcia k-napięta”, czyli unsatisfiable formuły K-CNF. O ile mi wiadomo, można uzyskać około

czasu na obalenie dowolnego obwodu podrzędnej głębokości UNSAT. Ale jak powiedziałem, gazeta ukaże się wkrótce.

{1.9}^{n}

$1.9^n$

2^{n / 2}

$2^{n/2}$

— Ryan Williams

Być może głupie pytanie, czy ten wynik (zasadniczo) zmierza w kierunku idei: przypuszczenia „NSETH” i „k-TAUT wymagają wykładniczych obwodów wielkości” wykluczają się wzajemnie? Czy też konstrukcja PRG łatwo pochłania potencjalną lukę między złożonością MA i NP k-TAUT?

— Joe Bebel,

Nie głupie pytanie! Krótka odpowiedź jest taka, że jeszcze nie wiem.

— Ryan Williams,

Przedruk można znaleźć, klikając ten link http://eccc.hpi-web.de/report/2016/002/

EDYCJA (1/24) Na życzenie, tutaj jest krótkie podsumowanie, zaczerpnięte z samego papieru, ale przeglądające wiele rzeczy. Załóżmy, Merlin może okazać się, że dla Arthur -variable arytmetyczna obwodem , jego wartość wszystkich punktach jest pewną tabeli elementów pola w czasie o , gdzie jest rozmiarem a jest stopniem wielomianu obliczonego przez $k$ $C$ $\{0,1\}^k$ $2^k$ $(s + 2^k) \cdot d$ $s$ $C$ $d$ $C$ . (Nazywamy to „krótkim nieinteraktywnym dowodem oceny partii” --- ocena w przypadku wielu zadań.) $C$

Następnie Merlin może rozwiązać SAT dla Artura w następujący sposób. Biorąc pod uwagę CNF dla zmiennych i klauzul , Merlin i Arthur najpierw konstruują obwód arytmetyczny na zmiennych stopnia co najwyżej , wielkość około , która przyjmuje sumę wszystkich przypisań do pierwsze zmiennych CNF (dodanie do sumy, gdy jest prawdziwe, i $\#$ $F$ $n$ $m$ $C$ $n/2$ $mn$ $mn \cdot 2^{n/2}$ $n/2$ $F$ $1$ $F$ $0$ gdy jest to fałsz). Za pomocą protokołu oceny partii Merlin może wówczas okazać się, że przybiera poszczególne wartości, na wszystkich logicznych zadań, w ciągu około czasu. Podsumowując wszystkie te wartości, otrzymujemy liczbę zadaniach SAT do . $C$ $2^{n/2}$ $2^{n/2}$ $2^{n/2} poly(n,m)$ $F$

$C$ $2^k$ $Q(x)$ $K$ $2^n$ $Q(x)$ $2^k \cdot d$ $Q$ $d$ $C$ $2^k$ $Q$

$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$

— Ryan Williams
źródło

W środkowej części (u góry) części 2 na stronie 6 wygląda na to, że R (x) należy zastąpić R (r).

Proszę o bezpośrednie przesyłanie komentarzy do manuskryptu; Nie sprawdzam wymiany stosów codziennie. Dzięki.

— Ryan Williams,

Czy mógłbyś podsumować główną ideę artykułu, aby udzielić bardziej samodzielnej odpowiedzi i ewentualnie zabezpieczyć się przed gniciem bitów?

— cody