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.[1] The low hierarchy starts from complexity class P and grows "upwards", while the high hierarchy starts from class NP and grows "downwards".[2]

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.[3]

It is not known whether these hierarchies cover all NP.

References

  1. ↑ Uwe Schöning (1983). "A Low and a High Hierarchy within NP". J. Comput. Syst. Sci. 27 (1): 14–28. doi:10.1016/0022-0000(83)90027-2.
  2. ↑ "Complexity Theory and Cryptology", by Jörg Rothe p. 232
  3. ↑ 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.