W parametryzowanej teorii złożoności podobną rolę odgrywa pytanie FPT kontra W, a w algebraicznej teorii złożoności pytanie VP kontra VNP.
Czas wielomianowy a praktyczna obliczalność Czas wielomianowy jest w teorii złożoności podstawowym formalnym progiem efektywnego obliczania, ale nie jest tym samym co praktyczna łatwość. Algorytm wielomianowy może mieć bardzo duży wykładnik lub stałe ukryte w notacji asymptotycznej, a twierdzenie o samym istnieniu takiego algorytmu mogłoby nie dawać od razu użytecznej procedury obliczeniowej.
Również odwrotna intuicja bywa zawodna: problem może mieć złe ograniczenia w najgorszym przypadku, a mimo to dobrze działać w wielu zastosowaniach. Dla niektórych reguł wyboru pivota metoda sympleks ma wykładnicze przykłady najgorszego przypadku, choć w praktyce często jest skuteczna. Samo programowanie liniowe ma natomiast znane algorytmy wielomianowe. Problem P vs NP nie rozstrzyga też automatycznie złożoności średniej: możliwe jest, że problem trudny w najgorszym przypadku ma większość instancji łatwych w praktyce. Russell Impagliazzo opisał kilka hipotetycznych „światów” złożoności średniej, od pełnej algorytmicznej łatwości po świat kryptograficznie trudnych instancji.