Klasa złożoności NEXP

11

Mam problem, który jest w NEXP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego). $^{\text{NP}}$

Czy jest coś znanego na temat NEXP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne problemy niż ogólne (biorąc pod uwagę maszynę NEXP i słowo, czy to się zgadza?). $^{\text{NP}}$ $^{\text{NP}}$

cc.complexity-theory reference-request complexity-classes nexp Hsien-Chih Chang 張顯之
źródło

2

Sprawdź pracę nad wykładniczą hierarchią czasu, na przykład ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Należy zauważyć, że

ma inną nazwę w literaturze (na podstawie charakterystyki naprzemiennej), a mianowicie

.

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

Naturalny -Complete problem decydując karę arytmetyka presburgera ze związkiem -quantifier prefiks (patrz tutaj ). Przebadano tutaj dalsze kompletne problemy związane z teorią baz danych . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
źródło

5

jest (prawdopodobnie) większy niż NEXP, ponieważ możemy zadawać pytania o wykładniczą długość z wyroczni. Ta NP w mocy jest praktycznie NEXP, więc np. Jednoczesne NEXP znajduje się w . $NEXP^{NP}$ $NEXP^{NP}$

domotorp
źródło

Ty dobrze argumentował w odpowiedzi na odpowiedź Peter Shor, że

jest prawdopodobnie ściśle mocniejszy niż

. Jestem jednak zmieszany. Wydaje się, że analogicznie powinno to oznaczać, że

jest większy niż

, choć (chyba) są one równe. Gdzie się tutaj mylę?

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

Huck Bennett

7

@Huck Wielomiany są zamknięte pod wielomiany. Wykładniki nie są. Mogę więc podać EXP wyroczni wykładniczo długi argument i może on działać wykładniczo w tym argumencie, który jest podwójnie wykładniczy w pierwotnym problemie.

Mark Reitblatt

@domotorp Myślałem, że

? Co powiesz na

?

N E X P^{N P} \subseteq N E X P^{E X P} = N E X P

$NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$

E X P^{E X P}

$EXP^{EXP}$

T ....

Problem polega na tym, że wejście wyroczni zostaje wypełnione, więc na przykład

.

D T I M E (2^{n})^{D T I M E (2^{n})} = D T I M E (2^{2^{n}})

$DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$

domotorp

@ Turbo Nie widzę teraz błędu, ale wygląda na to, że przy tej logice możemy udowodnić, że dla dowolnego

mamy

, czyli trochę podejrzane ... Może powinieneś zadać to pytanie.

f (n)

$f(n)$

D T I M E (f (n)) \subset P / p o l y

$DTIME(f(n))\subset P/poly$

domotorp

3

Rozwijając mój komentarz powyżej odrobinie: Jeśli masz tylko jedno zapytanie do -oracle (jak w Twoim przypadku), to wynika z prac Hemaspaandra, że problem jest w . Oznacza to, że problem jest Turing sprowadzić do żadnego problemu -hard. Myślę, że nie wiadomo, czy jest to prawdą dla wszystkich . $NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
źródło

1

Największy zapytanie A maszyna może wyroczni wykładnicza o długości wejściu. Moc wyroczni jest w tym wielomianowa, co również powinno być wykładnicze. Innymi słowy, . Dlatego inna maszyna powinna być w stanie symulować zarówno maszynę, jak i wyrocznię. $NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Edytowane dla nawiasów ...

Aubrey da Cunha
źródło

3

NTM tak nie działają. NTM podzielone, a jeśli jeden egzemplarz akceptuje całość, wszystko akceptuje. Po podzieleniu nie możesz spojrzeć na wyniki swoich kopii bez detekcji. Tak więc, jeśli wykonałem jedno zapytanie do maszyny NP i natychmiast zwróciłem odpowiedź przeciwną, jak byś to zasymulował?

Mark Reitblatt,

1

N P^{N P}

$NP^{NP}$

N P

$NP$

O tak. Symulując zapytanie Oracle, jeśli poprawny wynik to „nie”, wówczas wszystkie gałęzie zwrócą „nie”. Z drugiej strony, jeśli poprawny wynik to „tak”, wówczas co najmniej jedna gałąź zwróci tak. W szczególności niektórzy mogą zwrócić nie. Zatem, gdy sugeruje @Mark, negujesz wynik zapytania, prawdopodobnie uzyskasz fałszywe alarmy.

Aubrey da Cunha,

Klasa złożoności NEXP

Odpowiedzi: