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,

Odpowiedzi:

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