♯P - ♯P
v teorie výpočetní složitosti, třída složitosti #P (vyslovuje se „ostré P“ nebo někdy „číslo P“ nebo „hash P“) je množina počítání problémů spojené s rozhodovací problémy v sadě NP. Formálněji #P je třída funkčních problémů formuláře "výpočet" F(X) ", kde F je počet akceptačních cest a nedeterministický Turingův stroj běží dovnitř polynomiální čas. Na rozdíl od většiny známých tříd složitosti nejde o třídu rozhodovací problémy ale třída funkční problémy. Nejobtížnější, reprezentativní problémy této třídy jsou ♯P-kompletní.
Vztah k problémům s rozhodováním
An NP rozhodovací problém má často formu „Existují nějaká řešení, která splňují určitá omezení?“ Například:
- Existují nějaké podmnožiny seznamu celých čísel, které se sčítají až k nule? (problém podmnožiny )
- Existují nějaké Hamiltonovské cykly v daném graf s cenou nižší než 100? (problém obchodního cestujícího )
- Existují nějaká přiřazení proměnných, která splňují dané CNF (konjunktivní normální forma) vzorec? (Booleovský problém uspokojivosti nebo SAT)
- Má jednorozměrný skutečný polynom nějaké pozitivní kořeny? (Kořenový nález )
Korespondence #P funkční problémy se ptají „kolik“, spíše než „je jich vůbec“. Například:
- Kolik podskupin ze seznamu celých čísel se sčítá až k nule?
- Kolik hamiltoniánských cyklů v daném grafu stojí méně než 100?
- Kolik přiřazení proměnných splňuje daný vzorec CNF?
- Kolik kořenů jednorozměrného skutečného polynomu je kladných?
Jak je to těžké?
Je zřejmé, že #P problém musí být alespoň tak tvrdý jako odpovídající NP problém. Pokud je snadné spočítat odpovědi, pak musí být snadné zjistit, zda existují nějaké odpovědi - stačí je spočítat a zjistit, zda je počet větší než nula. Některé z těchto problémů, jako např kořenový nález, jsou natolik snadné, že se do nich dostanete FP zatímco ostatní ano ♯P-kompletní.
Jedním z důsledků Todova věta je to a polynomiální čas stroj s a #P věštec (P#P) může vyřešit všechny problémy v PH, celá polynomiální hierarchie. Ve skutečnosti musí stroj s polynomiálním časem udělat jen jeden #P dotaz na vyřešení jakéhokoli problému ve Windows PH. To naznačuje extrémní obtížnost řešení #P-úplné problémy přesně.
Překvapivě někteří #P problémy, které jsou považovány za obtížné, odpovídají snadným (například lineární čas) P problémy. Další informace o tom viz # P-kompletní.
Nejbližší třída problémového rozhodování #P je PP, který se ptá, zda většina (více než polovina) výpočetních cest přijímá. Toto najde nejvýznamnější bit v #P problémová odpověď. Třída rozhodovacího problému ⊕P (vyslovuje se „Parity-P“) místo toho požaduje nejméně významný kousek #P Odpovědět.
Formální definice
#P je formálně definována takto:
- #P je sada všech funkcí takový, že existuje polynomiální čas nedeterministický Turingův stroj takové, že pro všechny , se rovná počtu přijímajících poboček v výpočetní graf na .[1]
#P lze také ekvivalentně definovat jako verifer. Rozhodovací problém je v NP pokud existuje polynomiální čas, který lze zkontrolovat osvědčení k dané problémové instanci - tj. NP zeptá se, zda existuje důkaz o členství pro vstup, který lze zkontrolovat na správnost v polynomiálním čase. Třída #P ptá se Kolik certifikáty existují pro problémovou instanci, kterou lze zkontrolovat na správnost v polynomiálním čase.[1] V tomto kontextu, #P je definována takto:
- #P je sada funkcí takový, že existuje polynom a polynomiální čas deterministický Turingův stroj , volal ověřovatel, tak, že pro každého , .[2] (Jinými slovy, se rovná velikosti sady obsahující všechny certifikáty polynomiální velikosti).
Dějiny
Třída složitosti #P byl poprvé definován Leslie Valiant v článku z roku 1979 o výpočtu trvalý a čtvercová matice, ve kterém to dokázal permanent je # P-kompletní.[3]
Larry Stockmeyer prokázal, že pro každý problém #P existuje a randomizovaný algoritmus pomocí věštce pro SAT, který dal instanci z a vrací s vysokou pravděpodobností číslo takhle .[4] Runtime algoritmu je polynomiální a . Algoritmus je založen na zbytkové hashové lemma.
Viz také
Reference
- ^ A b Barak, Boaz (jaro 2006). "Složitost počítání" (PDF). Computer Science 522: Computational Complexity. Univerzita Princeton.
- ^ Arora, Sanjeev; Barak, Boaz (2009). Výpočetní složitost: moderní přístup. Cambridge University Press. p. 344. ISBN 978-0-521-42426-4.
- ^ Leslie G. Valiant (1979). "Složitost výpočtu stálé". Teoretická informatika. Elsevier. 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6.
- ^ Stockmeyer, Larry (listopad 1985). „Při přibližných algoritmech pro #P“ (PDF). SIAM Journal on Computing. 14 (4): 849. doi:10.1137/0214060. Archivovány od originál (PDF) v roce 2009. Shrnutí ležel.