Dwa warianty NP

Oto dwie odmiany definicji NP. (Prawie na pewno) definiują odrębne klasy złożoności, ale moje pytanie brzmi: czy istnieją naturalne przykłady problemów, które pasują do tych klas?

(Mój próg, który jest tutaj naturalny, jest nieco niższy niż zwykle).

Klasa 1 (nadklasa NP): problemy ze świadkami wielomianowymi, których weryfikacja wymaga czasu wielobiegunowego, ale subsponencjalnego. Dla konkretności, powiedzmy czas . Jest to równoważne klasie języków rozpoznawanych przez maszyny niedeterministyczne, które wymagają czasu ale mogą jedynie zgadywać poli (n) niedeterministyczne. $n^{O(\log n)}$ $n^{O(\log n)}$

Czy istnieją naturalne problemy w klasie 1, o których nie wiadomo / nie uważa się, że występują zarówno w i ? $NP$ $DTIME(n^{O(\log n)})$

Klasa 1 to jak zwykle klasa języków. Natomiast klasa 2 to klasa problemów relacyjnych:

Klasa 2: Relacja binarna R = {(x, y)} należy do tej klasy, jeśli

Istnieje wielomian p taki, że (x, y) w R implikuje | y | wynosi co najwyżej p (| x |).
Istnieje algorytm czasu A (poli | | x |) taki, że dla wszystkich danych wejściowych x, jeśli istnieje taki, że (x, y) jest w R, to (x, A (x)) jest w R, i jeśli nie ma takiego y, to A (x) odrzuca.
Dla dowolnego algorytmu B czasu poli (| x |) istnieje nieskończenie wiele par (x, w), tak że B (x, w) różni się od R (x, w) (tutaj używam R do oznaczenia własnej cechy funkcjonować).

Innymi słowy, we wszystkich przypadkach łatwo jest znaleźć jakiegoś świadka, jeśli taki istnieje. A jednak nie wszyscy świadkowie dają się łatwo zweryfikować.

(Zauważ, że jeśli R jest w klasie 2, to rzut R na jego pierwszy czynnik jest po prostu w P. To właśnie miałem na myśli mówiąc, że klasa 2 jest klasą problemów relacyjnych.)

Czy istnieją naturalne problemy relacyjne w klasie 2?

— Joshua Grochow
źródło

Nie jestem pewien pytania. Czy chcesz problemów, które oczywiście występują w jednej z klas, ale nie w drugiej?

— Lev Reyzin

Nie. Dla każdej klasy osobno zastanawiam się, czy istnieją naturalne problemy, które pasują do klasy, ale nie wiadomo, czy pasują do innych standardowych klas złożoności. Na przykład chciałbym wiedzieć, czy istnieje naturalny problem w klasie 1, o którym nie wiadomo, że występuje w NP.

— Joshua Grochow

Myślę, że chcesz przepisać warunek 2 dla klasy 2, ponieważ w przeciwnym razie A może być trywialnym algorytmem, który zawsze odrzuca. Twój słowny opis poniżej wydaje się bardziej sensowny.

— Andy Drucker,

W przypadku klasy 2 jednym nieco głupim przykładem jest R (p, a) = {p jest wielomianem całkowitym, a jest w zakresie p, a | a | = O (poli (| p |)}. R jest w klasie 2, ale nierozstrzygalny.

— Andy Drucker,

Andy - dlaczego nie opublikować tego jako odpowiedzi zamiast komentarza?

— Joshua Grochow

Dla klasy 2 jest to jeden głupi przykład

R (p, a) = {p jest liczbą całkowitą wielomianową, a jest w zakresie p, a | a | = O (poli (| p |)}.

R należy do klasy 2, ale nie można go rozstrzygnąć.

— Andy Drucker
źródło

{x : | p (x) | \leq r (| p |)}

$\{x : |p(x)| \leq r(|p|)\}$

p

$p$

a = 0

$a = 0$

R (p, a)

$R(p, a)$

p = 0

$p = 0$

O tak. Tak też wcześniej się przekonałem :). Dzięki.

— Joshua Grochow

Prosiłbym o wyjaśnienie nieco warunku świadka w klasie 1. Wygląda na to, że jakikolwiek odpowiednio ograniczony problem ze współ-NP wydaje się załatwić sprawę, czy to jest to, co zamierzałeś?

$\log n$

— Magnus Wahlström
źródło

n^{O (\log n)}

$n^{O(\log n)}$

N P

$NP$

N P

$NP$

D T I M E (n^{O (\log n)})

$DTIME(n^{O(\log n)})$ (Odpowiednio zaktualizuję pytanie). Zastanawiam się, czy wersja jakiegoś innego sparametryzowanego problemu może załatwić sprawę, ale nie znam zbytnio sparametryzowanej złożoności.

— Joshua Grochow

$f$

$f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$

$\exists x \forall y f(x_1,x_2,\ldots, x_n,y_1,y_2,\ldots,y_m)$

Prawdopodobnie nie ma go w QP, ponieważ może wyrażać wszystkie problemy w NP, i prawdopodobnie nie ma go w NP, ponieważ może wyrażać wszystkie problemy w co-NTIME (polilog).

— Robin Kothari
źródło

f

$f$

n + m

$n+m$

x_{i}

$x_i$

y_{j}

$y_j$

Tak, chyba to by zadziałało.

— Robin Kothari,