Niskie i wysokie hierarchie

W teorii złożoności obliczeniowej , niska hierarchia i wysoka hierarchia poziomów złożoności zostały wprowadzone w 1983 roku przez Uwe Schöninga w celu opisania wewnętrznej struktury klasy złożoności NP . Niska hierarchia zaczyna się od klasy złożoności P i rośnie „w górę”, podczas gdy hierarchia wysoka zaczyna się od klasy NP i rośnie „w dół”.

Później te hierarchie zostały rozszerzone na zbiory poza NP.

Ramy hierarchii wysokich/niskich mają sens tylko przy założeniu, że P nie jest NP . Z drugiej strony, jeśli niska hierarchia składa się z co najmniej dwóch poziomów, to P nie jest NP.

Nie wiadomo, czy te hierarchie obejmują wszystkie NP.