Nízké a vysoké hierarchie - Low and high hierarchies

V teorie výpočetní složitosti, nízká hierarchie a vysoká hierarchie úrovně složitosti byly zavedeny v roce 1983 Uwe Schöning popsat vnitřní strukturu třída složitosti NP.^[1] Nízká hierarchie začíná od třída složitosti P a roste „nahoru“, zatímco vysoká hierarchie začíná od třídy NP a roste „dolů“. ^[2]

Později byly tyto hierarchie rozšířeny na sady mimo NP.

Rámec vysokých / nízkých hierarchií má smysl pouze za předpokladu, že P není NP. Na druhou stranu, pokud se nízká hierarchie skládá z alespoň dvou úrovní, pak P není NP.^[3]

Není známo, zda tyto hierarchie pokrývají všechny NP.

Reference

^ Uwe Schöning (1983). „Nízká a vysoká hierarchie v NP“. J. Comput. Syst. Sci. 27 (1): 14–28. doi:10.1016/0022-0000(83)90027-2.
^ „Teorie složitosti a kryptologie“, autor Jörg Rothe p. 232
^ Lane A. Hemaspaandra, "Lowness: měřítko pro NP-P", Novinky ACM SIGACT, 1993, sv. 24, č. 2, s. 11-14. doi:10.1145/156063.156064

P ≟ NP

Tento teoretická informatika –Vztahující se článek je pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] Uwe Schöning (1983). „Nízká a vysoká hierarchie v NP“. J. Comput. Syst. Sci. 27 (1): 14–28. doi:10.1016/0022-0000(83)90027-2.

[2] „Teorie složitosti a kryptologie“, autor Jörg Rothe p. 232

[3] Lane A. Hemaspaandra, "Lowness: měřítko pro NP-P", Novinky ACM SIGACT, 1993, sv. 24, č. 2, s. 11-14. doi:10.1145/156063.156064

[1]

[2]

[3]