W jakim stopniu zdolność obliczeniowa trudnych zadań pomaga w rozwiązywaniu łatwych zadań

Krótko mówiąc, pytanie brzmi: w jakim stopniu zdolność obliczeniowa do trudnych zadań naprawdę pomaga w rozwiązywaniu łatwych zadań. (Mogą istnieć różne sposoby uczynienia tego pytania interesującym i nietrywialnym, a oto jedna z takich prób).

Pytanie 1:

Rozważ obwód rozwiązywania SAT dla formuły z n zmiennymi. (Lub do znalezienia cyklu hamiltonowskiego dla wykresu z krawędziami.)$n$

Załóżmy, że każda bramka umożliwia obliczenie dowolnej funkcji boolowskiej na zmiennych. Dla konkretności weźmy .m = 0,6 $m$$m=0.6 n$

Hipoteza silnego wykładniczego czasu (SETH) zakłada, że ​​nawet przy tak silnych bramkach potrzebujemy wielkości obwodu wielobiegunowego. W rzeczywistości potrzebujemy rozmiaru co najmniej na każde ϵ . W pewnym sensie bramkowanie ułamka zmiennych, które reprezentują bardzo skomplikowane funkcje boolowskie (znacznie wykraczające poza kompletność NP) nie dają dużej przewagi.$\Omega (2^{(0.4-\epsilon) n})$$\epsilon.$

Możemy dodatkowo zapytać:

(i) Czy możemy mieć taki obwód o wielkości ? 2 ( 1 - ϵ ) n ?$2^{0.9 n}$$2^{(1-\epsilon)n}$

Odpowiedź „nie” będzie ogromnym wzmocnieniem SETH. Oczywiście może jest odpowiedź „tak”, której po prostu mi brakuje.

(ii) Jeśli odpowiedź na (i) brzmi TAK, to czy bramki obliczające dowolne funkcje boolowskie dają pewne korzyści w porównaniu z bramkami, które „tylko” obliczają (powiedzmy) dowolne funkcje NP; czy tylko mniejsze instancje samego SAT?

Kolejne próby pytaniem coś podobnego do pytań w .$P$

Pytanie 2:

Tak jak poprzednio, niech a dla konkretności wstaw m = 0,6 n . (Inne wartości m, takie jak m = n α, również są interesujące.) Rozważ następujące typy obwodów:$m< n$$m=0.6n$$m$$m=n^\alpha$

a) W jednym kroku możesz obliczyć dowolną funkcję boolowską na zmiennych.$m$

b) W jednym kroku możesz rozwiązać problemy SAT z zmiennymi. A może dowolny niedeterministyczny obwód wielomianu w m zmiennych.$m$$m$

c) W jednym kroku możesz wykonać dowolny obwód na zmiennych o wielkości m d ( d jest ustalony).$m$$m^d$$d$

d) W jednym kroku możesz wykonać zwykłe bramki boolowskie.

Zastanówmy się nad znalezieniem idealnego dopasowania dla wykresu z krawędziami. Dopasowanie ma obwód wielkości wielomianowej. Pytanie brzmi, czy wykładnik w takim algorytmie dopasowującym można poprawić, przechodząc z obwodów typu d) do obwodów typu c) i od obwodów wielkości c) do obwodów wielkości b) oraz z obwodów wielkości b ) do obwodów o rozmiarze a).$n$

(Może to być związane ze znanymi problemami dotyczącymi obliczeń równoległych lub wyroczni).

Zliczając powinieneś być w stanie obliczyć około funkcje w takich obwodach rozmiar s więc Przypuszczam y = 2 n - m powinno wystarczyć, aby obliczyć wszystkie funkcje.$2^{2^m \cdot s}$$s$$s=2^{n-m}$