Czy NP jest w ?

Czy NP jest w $DTIME(n^{poly\log n})$ ?

$DTIME(n^{polylogn})$ jest znany jako$QP$ (quasi-wielomian).

$NP\not \subset QP$$P\neq NP$

Niektóre typowe przypuszczenia, takie jak hipoteza wykładniczego czasu, sugerują .$NP\not \subset QP$

Innym dobrym powodem, aby sądzić, że jest to, że implikuje , a ten drugi jest uważany za bardzo mało prawdopodobny. Tę implikację można udowodnić za pomocą argumentu wypełniającego, patrz np. W dowodzie Twierdzenia 2 w następującym dokumencie:N P ⊆ Q P E X P = N E X $NP\not\subseteq QP$$NP\subseteq QP$$EXP=NEXP$

H. Buhrman i S. Homer, „Obwody wielobiegunowe, prawie rzadkie wyrocznie i hierarchia wykładnicza”, Podstawy technologii oprogramowania i informatyki teoretycznej, Springer LNCS obj. 652, 1992, s. 116–127, pdf