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$ $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^{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 . (Inne wartości takie jak 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 zmiennych. $m$ $m$

c) W jednym kroku możesz wykonać dowolny obwód na zmiennych o wielkości ( 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).

cc.complexity-theory dc.parallel-comp

— Gil Kalai
źródło

Właściwie Mocny ETH nie jest tak silna: to po prostu mówi, że nie może mieć jednolitego algorytmu działa w

czas dla SAT z

klauzul dla wszystkich

. Zezwalanie na dowolne funkcje boolowskie na małych zestawach zmiennych stawia cię w nierównomiernym obwodzie obwodu. „Niejednorodny SETH” jest ciekawym wariantem, ale nie sądzę, aby został jeszcze dokładnie zbadany.

O ({1.9999}^{n})

$O(1.9999^n)$

c n

$cn$

c

$c$

— Ryan Williams,

Drogi Rayanie, tak, po prostu czuję się bardziej komfortowo, biorąc pod uwagę niejednolity przypadek. Brak odpowiedzi na pytanie 1 będzie ogromnym wzmocnieniem niejednolitego SETH. (Myślałem, że niejednolity SETH jako wzmocnienie SETH, ale może się myliłem.) Możliwe, że możesz przeformułować Pytania 1 i 2 dla jednolitych algorytmów. W każdym razie być może przy tak mocnych wersjach SETH i nierównomiernym SETH będzie można znaleźć kontrprzykład.

— Gil Kalai,

Myślę, że chcesz uważać na to, co oznacza

: w SETH oznacza liczbę zmiennych, w powyższym wydaje się oznaczać długość wejściową. Jeśli dopuścisz bramki, które mogą „obliczyć SAT dla instancji zmiennej

zmiennej”, trywialne jest uzyskanie obwodu o głębokości

dla zmiennej

zmiennej SAT: weź OR dla wszystkich możliwych przypisań do zmiennych

zmiennej i użyj bramek SAT, aby rozwiązać SAT na pozostałych

zmiennych. Ale prawdopodobnie nie tego szukasz ... Czy to jest?

n

$n$

.1 n

$.1n$

2^{.9 n}

$2^{.9n}$

n

$n$

.9 n

$.9n$

.1 n

$.1n$

— Ryan Williams,

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

— Boaz Barak
źródło

Cześć, @Boaz Barak. Czy miałbyś coś przeciwko, jeśli połączyłem twoje dwa konta na tej stronie?

— Lew Reyzin

Dzięki Boaz. Myślę, że duch tego pytania jest następujący: jeśli zejdziesz znacznie poniżej tego, co jest potrzebne do obliczenia wszystkich funkcji, czy nadal możesz obliczyć NP całkowitą funkcję.

— Gil Kalai,