Czy istnieje problem obliczeniowy, który występuje w quasi-wielomianowym czasie, ale (być może) go nie ma

Czas quasi-wielomianowy, w skrócie QP, jest klasą złożoności na deterministycznej maszynie Turinga. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

Podczas gdy βP jest klasą złożoności o ograniczonym niedeterminizmie. Oto dokładna definicja: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Łatwo zauważyć, że dowolna maszyna βP może być symulowana przez maszynę QP, a mianowicie βP $\subseteq$ QP.

Ale czy mamy przykład problemu, który występuje w QP, ale nie w βP, nawet jeśli nie mamy dokładnego dowodu, że problem nie występuje w βP?

cc.complexity-theory complexity-classes Arthur Kexu-Wang
źródło

Niech f będzie funkcją number_of_states_ i rozważmy problem

$\hspace{2.36 in}$ „Czy M zatrzymuje się co najwyżej (f (M))

^{\log (f (M))}

$^{\hspace{.02 in}\log(\hspace{.04 in}f(M))}$ kroki „?.

Odpowiedzi:

Chociaż nie znam konkretnego (przypuszczalnego) przykładu w $QP-\beta P$ , wciąż istnieją przekonujące dowody na to $\beta P$ jest właściwym podzbiorem $QP$ . Mianowicie, klasy te zachowują się zupełnie inaczej w stosunku do $NP$ :

$\bullet$ Z definicji wynika, że $\beta P\subseteq NP$ .

$\bullet$ Z drugiej strony, $QP\subseteq NP$ nie jest znane i byłoby bardzo trudne do udowodnienia, ponieważ implikuje $P\neq NP$ . (W rzeczywistości jest to nawet silniejsze stwierdzenie niż $P\neq NP$ .)

Takie zupełnie inne zachowanie w stosunku do $NP$ wydaje się stanowić dość silny powód, by w to wierzyć $\beta P\neq QP$ .

Andras Farago
źródło

Wydaje się również mało prawdopodobne

β P

$\beta P$ do zamknięcia pod uzupełnieniem.

Emil Jeřábek

Ponieważ, jak wspomniałeś

Q P \subseteq N P

$QP\subseteq NP$ sugerować

P \neq N P

$P\neq NP$ . Jako następstwo, jaki byłby wynik

N P \subseteq Q P

$NP \subseteq QP$ lub

N P \subset Q P

$NP \subset QP$ sugerować w hierarchii złożoności i czy miałoby to jakikolwiek wpływ na

P v s N P

$P vs NP$ problem?

TheoryQuest1

Tak. Mamy taki problem. Jest to problem z izomorfizmem grafów. Babai udowodnił, że GI jest w QP . Rozumiem, że dowód Babai'a nie ogranicza górnej granicy niedeterminizmu ( $\beta P$ ) w sprawie złożoności oznaczenia geograficznego.

Nie mamy dowodu, że GI jest w środku $\beta P$ . Co więcej, nie mamy dowodu na to, że GI nie da się rozwiązać za pomocą niedeterminizmu pollogarytmicznego.

Zobacz ten powiązany post .

Ten post z teorii CS autorstwa @ Salamon wskazuje, że nawet nie wiemy, czy można decydować o GI za pomocą niedeterminizmu opartego na pierwiastkach kwadratowych, a tym bardziej niedeterminizmu polikarytmicznego.

Mohammad Al-Turkistany
źródło

Myślę jednak, że wiele osób przypuszcza, że GI jest w P.

Thomas

@Thomas Babai w swoim artykule wskazał, że jest przeciwny temu przypuszczeniu.

Mohammad Al-Turkistany

Czy jesteś pewien, że algorytm Babai nie jest włączony?

β P

$\beta P$ ?

Joshua Grochow

@ MohammadAl-Turkistany Jak na ironię, cytowane przez ciebie pytanie dotyczące MO (zarówno w odpowiedzi, jak i w komentarzu) pochodzi od samego OP z 10 miesięcy temu i nie ma odpowiedzi (do dziś). Nie jestem pewien, jak bardzo to potwierdza twoją argumentację - oznacza to tylko, że „nie mamy dowodu na to, że GI jest w

β P

$\beta P$ przywoływane w MathOverflow „w najlepszym wypadku.

Clement C.

@JoshuaGrochow Tak, komentarz jest bardziej szczegółowy (wskazując konkretną część dotyczącą stopnia). Ale odpowiedź tylko odwołuje się do pytania na temat MO jako tego, co uważam za silną wskazówkę dla twierdzenia, że nie ma dowodu - co wydaje mi się okrągłe.

Clement C.