Low and high hierarchies

In the computational complexity theory, the low hierarchy and high hierarchy of complexity levels were introduced in 1983 by Uwe Schöning to describe the internal structure of the complexity class NP.{{cite journal

| doi = 10.1016/0022-0000(83)90027-2

| author = Uwe Schöning

| title = A Low and a High Hierarchy within NP

| journal = J. Comput. Syst. Sci.

| volume = 27

| issue = 1

| year = 1983

| pages = 14–28

| doi-access=

}} The low hierarchy starts from complexity class P and grows "upwards", while the high hierarchy starts from class NP and grows "downwards"."Complexity Theory and Cryptology", by Jörg Rothe [https://books.google.com/books?doi=1mMz89RTyaYC&pg=PA232&dq=low++high+hierarchy+within+NP+complexity&lr= p. 232]

Later these hierarchies were extended to sets outside NP.

The framework of high/low hierarchies makes sense only under the assumption that P is not NP. On the other hand, if the low hierarchy consists of at least two levels, then P is not NP.Lane A. Hemaspaandra, "Lowness: a yardstick for NP-P", ACM SIGACT News, 1993, vol. 24, no.2, pp. 11-14. {{doi|10.1145/156063.156064}}

It is not known whether these hierarchies cover all NP.