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