PH (složitost) - PH (complexity)

v teorie výpočetní složitosti, třída složitosti PH je spojení všech tříd složitosti v polynomiální hierarchie:

PH byl poprvé definován Larry Stockmeyer.[1] Je to zvláštní případ hierarchie ohraničený střídavý Turingův stroj. Je obsažen v P#P = PPP (podle Todova věta; třída problémů, které jsou určitelné polynomiálním časem Turingův stroj s přístupem k a #P nebo ekvivalentně PP věštec ) a také v PSPACE.

PH má jednoduchý logická charakterizace: je to sada jazyků vyjádřitelných pomocí logika druhého řádu.

PH obsahuje téměř všechny dobře známé třídy složitosti uvnitř PSPACE; zejména obsahuje P, NP, a co-NP. Obsahuje dokonce pravděpodobnostní třídy jako BPP a RP. Existují však určité důkazy BQP, třída problémů řešitelných v polynomiálním čase a kvantový počítač, není obsažen v PH.[2][3]

P = NP kdyby a jen kdyby P = PH.[4] To může zjednodušit potenciální důkaz P ≠ NP, protože je nutné pouze oddělit P z obecnější třídy PH.

Reference

  1. ^ Stockmeyer, Larry J. (1977). Msgstr "Hierarchie polynomiálního času". Teor. Comput. Sci. 3: 1–22. doi:10.1016 / 0304-3975 (76) 90061-X. Zbl  0353.02024.
  2. ^ Aaronson, Scott (2009). "BQP a polynomiální hierarchie". Proc. 42. symposium o teorii práce na počítači (STOC 2009). Sdružení pro výpočetní techniku. 141–150. arXiv:0910.4698. doi:10.1145/1806689.1806711. ECCC  TR09-104.
  3. ^ https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/
  4. ^ Hemaspaandra, Lane (2018). „17.5 Třídy složitosti“. V Rosen, Kenneth H. (ed.). Příručka diskrétní a kombinatorické matematiky. Diskrétní matematika a její aplikace (2. vyd.). CRC Press. str. 1308–1314. ISBN  9781351644051.

Obecné odkazy