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

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 , ?$1^{n}$$C$$\varphi$$|\varphi| \leq n$$C(\varphi) = SAT(\varphi)$

(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. $n$$n$$\leq 2^{O(n)}$$O(2^n 2^M)$$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?$o(2^n 2^M)$$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 $C$$f$$C'$$C$$n$

• P / p o l $NP$ a$P/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 $NP \subseteq P/poly$$NP \subseteq P$$P$ , ale P ≠ N P - czyli N P zawiera obwody wielomian rozmiarach lecz nie znajdują się w czasie wielomianowym.$NP \subseteq P/poly$$P \neq NP$$NP$

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^{\Omega(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))$$2^{o(M)}$ .$T(n)=2^{n^{o(1)}}$