PH (Komplexität)

Im Computerkomplexitätstheorie, das Komplexitätsklasse PH ist die Vereinigung aller Komplexitätsklassen in der Polynomhierarchie:

PH wurde zuerst definiert von Larry Stockmeyer.[1] Es ist ein besonderer Fall von Hierarchie von Begrenzte alternierende Turing -Maschine. Es ist in enthalten in P#P = PPp (durch Todas Satz; Die Klasse von Problemen, die durch eine Polynomzeit licht Turing Maschine mit Zugang zu a #P oder gleichwertig Pp Orakel) und auch in PSPACE.

PH hat ein einfaches logische Charakterisierung: Es ist die Reihe von Sprachen, Logik zweiter Ordnung.

PH enthält fast alle bekannten Komplexitätsklassen im Inneren PSPACE; Insbesondere enthält es P, Np, und Co-NP. Es enthält sogar probabilistische Klassen wie z. BPP und RP. Es gibt jedoch einige Beweise dafür BQP, die Klasse der Probleme, die in Polynomzeit von a löslich sind Quantencomputer, ist nicht in enthalten in PH.[2][3]

P = Np dann und nur dann, wenn P = PH.[4] Dies kann einen potenziellen Nachweis von vereinfachen P ≠ Np, da es nur notwendig ist, sich zu trennen P aus der allgemeineren Klasse PH.

Verweise

  1. ^ Stockmeyer, Larry J. (1977). "Die Polynom-Zeit-Hierarchie". Theor. Computer. Sci. 3: 1–22. doi:10.1016/0304-3975 (76) 90061-x. Zbl 0353.02024.
  2. ^ Aaronson, Scott (2009). "BQP und die Polynomhierarchie". Proc. 42. Symposium über die Computertheorie (STOC 2009). Verband für Rechenmaschinen. S. 141–150. Arxiv:0910.4698. doi:10.1145/1806689.1806711. ECCC TR09-104.
  3. ^ "Schließlich ein Problem, das nur Quantencomputer jemals lösen können". 21. Juni 2018.
  4. ^ Hemaspaandra, Lane (2018). "17.5 Komplexitätsklassen". In Rosen, Kenneth H. (Hrsg.). Handbuch für diskrete und kombinatorische Mathematik. Diskrete Mathematik und ihre Anwendungen (2. Aufl.). CRC Press. S. 1308–1314. ISBN 9781351644051.

Allgemeine Referenzen