Räkneproblem (komplexitet)
Inom beräkningskomplexitetsteori och beräkningsbarhetsteori är ett räkneproblem en typ av beräkningsproblem . Om R är ett sökproblem då
är motsvarande räknefunktion och
betecknar motsvarande beslutsproblem.
Observera att c R är ett sökproblem medan # R är ett beslutsproblem, men c R kan C Cook-reduceras till # R (för lämplig C ) med hjälp av en binär sökning (orsaken till att # R är definierad som den är, snarare än att vara grafen för c R , är att göra denna binära sökning möjlig).
Räkna komplexitetsklass
Om NX är en komplexitetsklass associerad med icke-deterministiska maskiner så är #X = { #R | R ∈ NX } är uppsättningen räkneproblem associerade med varje sökproblem i NX . I synnerhet #P klassen av räkneproblem som är förknippade med NP- sökproblem. Precis som NP har NP-kompletta problem via många-en-reduktioner , har #P fullständiga problem via sparsamma reduktioner , problemtransformationer som bevarar antalet lösningar.