Problém počítání (složitost) - Counting problem (complexity) - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: Složitost „problému s počítáním“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Října 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie výpočetní složitosti a teorie vypočítatelnosti, a počítání problém je typ výpočetní problém. Li R je problém s hledáním pak

${ displaystyle c_ {R} (x) = vert {y mid R (x, y) } vert ,}$

je odpovídající funkce počítání a

${ displaystyle #R = {(x, y) střední y leq c_ {R} (x) }}$

označuje odpovídající rozhodovací problém.

Všimněte si, že C_R je problém s vyhledáváním, zatímco #R je však problém s rozhodnutím C_R může být C Cook-snížené do #R (podle potřeby C) používat binární vyhledávání (důvod #R je definován tak, jak je, spíše než jako graf C_R, je umožnit toto binární vyhledávání).

Třída složitosti počítání

Li NX je třída složitosti spojená s nedeterministický stroje #X = {#R | R ∈ NX} je sada problémů s počítáním spojených s každou z nich problém s hledáním v NX. Zejména, #P je třída počítání problémů spojených s NP problémy s vyhledáváním. Stejně jako NP NP-kompletní problémy prostřednictvím mnoho-jedna redukce, #P má úplné problémy prostřednictvím šetrné snižování, transformace problémů, které zachovávají počet řešení.

Viz také

• GapP

externí odkazy

• "problém počítání". PlanetMath.
• "počítání třídy složitosti". PlanetMath.