Co wiadomo na temat złożoności znalezienia minimalnych obwodów dla SAT?

23

Co wiadomo o złożoności znalezienia minimalnych obwodów, które obliczają SAT do długości ? n

Bardziej formalnie: jaka jest złożoność funkcji, która, biorąc pod uwagę jako wejście, generuje minimalny obwód taki, że dla dowolnej formuły z , ?1nCφ|φ|nC(φ)=SAT(φ)

(Szczególnie interesują mnie dolne granice).

Naiwny deterministyczny algorytm (oblicz SAT za pomocą siły brutalnej do długości , a następnie wypróbuj wszystkie obwody w kolejności wielkości, aż znajdziesz taki, który poprawnie oblicza SAT do długości ) zajmuje czasu na obliczenie SAT, a następnie dodatkowy czas na znalezienie obwodu minimalnego, gdzie jest rozmiarem obwodu minimalnego. nn2O(n)MO(2n2M)M

Czy istnieje algorytm deterministyczny, który znajduje minimalne obwody dla SAT, których czas działania wynosi , gdzie jest rozmiarem minimalnego obwodu? Czy może to oznacza załamanie się złożoności?Mo(2n2M)M


Oto dwie rzeczy, które, choć związane z moim pytaniem, zdecydowanie nie są tym, o co pytam (co, jak sądzę, dlaczego tak trudno było mi szukać):

  • Układ minimalizacji problemu: podany obwód (lub funkcją podano w swojej tabeli prawdy, lub kilku innych wariantów) znajdują minimalny obwód Obliczanie samą funkcję jak . Nawet gdyby minimalizacja obwodu była łatwa, niekoniecznie oznaczałoby to, że powyższe zadanie jest łatwe, ponieważ nawet obliczenie funkcji, którą chcemy zminimalizować (SAT do długości ) uważa się za trudne, podczas gdy w problemie minimalizacji obwodu funkcja chcesz zminimalizować jest bezpłatny (podany jako dane wejściowe).f C C nCfCCn

  • P / p o l yNP aP/poly . Moje pytanie nie dotyczy jedynie wielkości minimalnego obwodu; chodzi o złożoność znalezienia minimalnego obwodu, niezależnie od jego wielkości. Oczywiście, jeśli możemy obliczyć minimalne obwody w czasie wielomianowym, wówczas (a właściwie N P P , ponieważ rodzina obwodów jest jednorodna P ), ale odwrotność nie musi być prawdziwa. Rzeczywiście, uważam, że Immerman i Mahaney jako pierwsi zbudowali wyrocznię, w której N P P / p oNPP/polyNPPP , ale P N P - czyli N P zawiera obwody wielomian rozmiarach lecz nie znajdują się w czasie wielomianowym.NPP/polyPNPNP

Joshua Grochow
źródło
Chcesz bezwarunkowe dolne granice? (Oczywiście złożoność czasowa jest mniej ograniczona przez złożoność obwodów SAT, ale nie wiemy w zasadzie nic konkretnego o tym drugim.)
Ryan Williams
@Ryan: Jak to często bywa, bezwarunkowe byłoby fajne, ale prawdopodobnie jest to zbyt wiele, na co można liczyć. Dodałem drugie pytanie dotyczące złożoności pod względem wielkości wyjściowej (= rozmiar minimalnego obwodu), aby pomóc w wyjaśnieniu na przykład.
Joshua Grochow
3
Ach, rozumiem teraz. To bardzo miłe pytanie. Bshouty i in. Mogą być w stanie poprawić naiwne powiązania, wykorzystując pomysły z algorytmów uczenia się obwodów SAT. Jeśli już znalazłeś obwód dla SAT do pewnego rozmiaru, być może możesz go uruchomić i użyć go, aby bardziej efektywnie znaleźć obwód o większym rozmiarze.
Ryan Williams,

Odpowiedzi:

12

Załóżmy, że nie można rozwiązać SAT znacznie szybciej nierównomiernie niż jednolicie. Oznacza to, że TM M rozwiązuje SAT w czasie T (n), a najmniejszy obwód dla SAT ma rozmiar T '(n), który nie jest dużo mniejszy niż T (n) (powiedzmy, - dotyczy to w szczególności sytuacji, gdy najmniejszy obwód do rozwiązywania SAT ma rozmiar 2 Ω ( n ), co może być bardzo prawdziwe).T(n)=poly(T(n))2Ω(n)

Tak więc można uzyskać „prawie” minimalny obwód, po prostu uruchamiając kanoniczną symulację M przez obwód, w czasie, który jest zasadniczo optymalny (tyle czasu, ile potrzeba na zapisanie wyniku). Właśnie z tego powodu zgaduję, że nie będzie dolnej granicy tego pytania w oparciu o jakiekolwiek „miłe” założenie. Nie wiem jednak, jak przejść z „prawie minimalnego” do faktycznie minimalnego. Jednym ze sposobów będzie wykorzystanie faktu, że znalezienie obwodu do rozmiaru jest pytaniem w hierarchii wielomianowej,ST(T(n))2o(M) .T(n)=2no(1)

Boaz Barak
źródło