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?

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$.

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.