Czy istnieje taka wyrocznia, że SAT nie jest nieskończenie często w czasie sub wykładniczym?

Zdefiniuj $io$ - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”). $SUBEXP$ $L$ $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ $n$ $L$ $L'$ $n$

Czy istnieje wyrocznia $A$ taka, że $NP^A \not\subset io$ - $SUBEXP^A$ ? Jeśli wyposażymy SAT w wyrocznię $A$ w zwykły sposób, czy możemy powiedzieć, że $SAT^A$ nie ma w tej klasie?

(Zadaję tutaj osobne pytania, ponieważ musimy zachować ostrożność przy nieskończenie częstych zajęciach czasowych: tylko dlatego, że masz redukcję z problemu $B$ do problemu $C$ a $C$ można rozwiązać nieskończenie często, może nie być tak, że $B$ można rozwiązać nieskończenie często bez dalszych założeń dotyczących redukcji: co zrobić, jeśli redukcja z $B$ „pomija” długości wejściowe, na których można rozwiązać $C$ ?)

cc.complexity-theory sat oracles Ryan Williams
źródło

wygląda na rozszerzenie lub odmianę pomysłu Baker Gill Solovay 1975? czy można to jakoś skontrastować?

vzn

Odpowiedzi:

Możesz wziąć wyrocznię A st NP = EXP ponieważ EXP nie znajduje się w io-subexp. W przypadku SAT zależy to od kodowania, na przykład jeśli jedyne prawidłowe instancje SAT mają parzystą długość, wówczas łatwo jest rozwiązać SAT na ciągach nieparzystych. Ale jeśli używasz języka takiego jak to powinieneś być w porządku. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Lance Fortnow
źródło

Czy masz jakieś odniesienia do pojęcia klas złożoności io separacji w literaturze? W szczególności nie jestem pewien, dlaczego

E X P ⊈ i o

$EXP \nsubseteq io$

. Ponadto, czy mamy (1)

S U B E X P

$SUBEXP$

T I M E (f (n)) ⊈ i o

$TIME(f(n)) \nsubseteq io$

dla odpowiednich funkcji f (n) i (2)

oznacza

(lub przynajmniej

T I M E (\frac{f (n)}{\log (f (n))})

$TIME(\frac{f(n)}{\log(f(n))})$

N P \subseteq i o

$NP \subseteq io$

P

$P$

P = N P

$P = NP$

N P \subseteq P / p o l y

$NP \subseteq P/ poly$

Michael Wehar

Myślę, że moim głównym zamieszaniem jest to, dlaczego nie każdy algorytm

ma algorytm

, który rozwiązuje problem tylko dla zestawu długości wejściowych

gdzie

jest zestawem

E X P

$EXP$

C o m p l e t e

$Complete$

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

X

$X$

E X P

$EXP$

C o m p l e t e

$Complete$

Michael Wehar

Innymi słowy, algorytm

nie pomaga nam, ponieważ musielibyśmy zdecydować

, aby wiedzieć, jak korzystać z algorytmu

Ale nie zdziwiłbym się, gdyby moje dotychczasowe prace rozwiązały moje zapytanie.

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

i o

$io$

S U B E X P

$SUBEXP$

Michael Wehar

@RyanWilliams Cześć Ryan, jakieś myśli? Dziękuję za Twój czas. :)

Michael Wehar

@RyanWilliams Dzięki za komentarz! Pomogło i myślę, że się udało. Teraz wydaje się, że argument wcale nie zależał od EXP i można to uogólnić, aby udowodnić coś w rodzaju (1). Ale kluczowym punktem była „przeciwna wartość na co najmniej jednym wejściu tej długości ”. Innymi słowy, argument w mojej głowie zależy od zdefiniowania io jako nieskończenie wielu długości wejściowych (nie tylko nieskończenie wielu wejściowych). Nadal nie mam pojęcia o czymś takim jak (2). Jeszcze raz dziękuję i życzę miłego dnia / nocy. :)

Michael Wehar

Nie musisz iść na całość, którą sugerował Lance. Na przykład, w stosunku do losowej wyroczni, użycie wyroczni jako funkcji jednokierunkowej (powiedzmy, ocenianej na kolejnych pozycjach bitów) jest wykładniczo trudne do odwrócenia na wszystkich, ale nieskończenie wielu długościach.

Ten problem bezpośrednio redukuje się do SAT na tej samej długości wejścia, więc wynika z tego, że SAT ^ A nie jest nieskończenie często sub-exp.

Russell Impagliazzo
źródło

Powinienem powiedzieć, że liczba wejść do obwodu jest taka sama, a nie całkowita wielkość instancji. Jeśli jednak możesz uzupełniać rozmiary obwodów poprzez dodawanie klauzul redundantnych, powinieneś być w stanie uczynić dowolny stały kod rozmiaru wejściowego powiązaną funkcją jednokierunkową.

Russell Impagliazzo

Czy istnieje taka wyrocznia, że ​​SAT nie jest nieskończenie często w czasie sub wykładniczym?

Odpowiedzi:

Czy istnieje taka wyrocznia, że SAT nie jest nieskończenie często w czasie sub wykładniczym?