Czy obwody quasi-wielomianowe dla 3-SAT są banalne?

Załóżmy, że rozważamy 3-SAT ze zmiennymi i klauzulami . Badam metodę, która wydaje się zajmować czas / przestrzeń celu rozwiązania dowolnego problemu SAT pasującego do tego opisu, z błędem, który można dostosować do dowolnej kwoty. Jest jednak pewien haczyk. $v$ $c$ $O(v^{2+\log c})$

Ta metoda wymaga zestawu wstępnie obliczonych wartości, po których może rozwiązać dowolny problem 3-SAT pasujący do powyższego opisu. Wstępnie obliczone wartości są zestawem wielkości przy czym każda wartość zajmuje przestrzeń . Prawdziwy problem polega na tym, że obliczenie każdej z tych wartości może zająć . Jest szansa, że znajdę sposób na przyspieszenie tych obliczeń. $O(v^{2+\log c})$ $O(1)$ $O(2^v)$

Myślę, że same granice przekraczają górne granice przedstawione w tym pytaniu (dla małego ). Zastanawiam się więc, czy istnieje trywialny sposób na osiągnięcie górnych granic, które opisuję, jeśli pozwolimy na wstępne obliczenia ? $c$ $O(v^{2+\log c})$

Chciałbym kontynuować te badania i mam nadzieję, że opublikuję moje wyniki, jeśli wszystko się powiedzie, ale najpierw chciałbym wiedzieć, czy istnieje trywialny sposób, aby zrobić to dobrze, czy lepiej.

AKTUALIZACJA

Oprócz badań tego algorytmu studiowałem powiązane problemy. Zadałem to pytanie na stronie IT Security firmy StackExchange dotyczącej łamania haseł i SAT, jeśli jesteś zainteresowany. Przynajmniej jedna z odpowiedzi odzwierciedla to.

ds.algorithms sat upper-bounds Matt Groff
źródło

Mówisz, że zajmuje to czas / przestrzeń O (N ^ 2 + logc) ... Więc nie ma go w PSPACE? Ale w QSPACE (Quasi-Space)?

Tayfun Zapłać

@Tayfun Pay: Działa w

. Jest to algorytm deterministyczny, który daje modułowi wyników pierwszą liczbę

(zauważ, że ten wynik wystarcza, aby reszta algorytmu mogła określić zadowalające przypisanie). Można go uruchomić dla dowolnej liczby pierwszych. Ubieganie o więcej niż jedną liczbę pierwszą zwiększa szansę na znalezienie satysfakcjonującego zadania. Ma szansę na znalezienie zadowalającego przypisania

O (v^{(2 + \log c)})

$O(v^{(2+\log c)})$

p

$p$

(p - 1) / p

$(p-1)/p$

Matt Groff,

Czy potrzebuje O (N ^ (2 + log (c))) SPACJA?

Tayfun Pay

@Tayfun Pay: Tak. Nie znalazłem jeszcze sposobu na zmniejszenie przestrzeni.

Matt Groff

Proponuję zmienić tytuł na bardziej odpowiedni. Obecny tytuł nie wydaje się atrakcyjny, a samo pytanie tak wygląda.

Yoshio Okamoto

Jeśli to, co studiujesz, zadziałało, na pewno nie byłoby trywialne.

$n^{O(\log n)}$ $NP$ $n^{O(\log^c n)}$

$2^{2^n}$ $2^{O(\log^2 n)}$ $n$ $2^{O(\log^2 n)}$

Co rozumiesz przez „w ramach błędu, który można dostosować do dowolnej kwoty”? Czy algorytm jest losowy?

Ryan Williams
źródło

x

$x$

1 / (2^{x})

$1/(2^x)$

W jaki sposób algorytm nie może być losowy, a mimo to można go uruchamiać wielokrotnie, aby zmniejszyć błąd? Myślę, że prawdopodobnie musiałbyś podać przynajmniej kilka dodatkowych szczegółów, aby zrozumieć swoje pytanie.

Ryan Williams

p

$p$

p

$p$

$\;$

(p - 1) / p

$(p-1)/p$

$\hspace{0.9 in}$

p

$p$

$\;\;$

p

$p$

n

$n$

B P P \subset P / p o l y

$BPP \subset P/poly$

3 / 4

$3/4$

100 n

$100n$

2^{O (\log^{2} n)}

$2^{O(\log^2 n)}$

1 / 2^{n}

$1/2^n$

Ryan Williams

Czy obwody quasi-wielomianowe dla 3-SAT są banalne?

Odpowiedzi: