Co wiadomo o złożoności znalezienia minimalnych obwodów, które obliczają SAT do długości ?
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 , ?
(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. 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?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 n
P / p o l y a . 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 o , ale P ≠ N P - czyli N P zawiera obwody wielomian rozmiarach lecz nie znajdują się w czasie wielomianowym.
źródło
Odpowiedzi:
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,S T(T(n)) 2o(M) .T(n)=2no(1)
źródło