Πρόβλημα απαρίθμησης

Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα απαρίθμησης είναι ένα είδος υπολογιστικού προβλήματος. Έστω ότι το R είναι ένα πρόβλημα αναζήτησης. Τότε το

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

είναι η αντίστοιχη συνάρτηση απαρίθμησης και το

$\#R=\{(x,y)\mid y\leq c_{R}(x)\}$

υποδηλώνει το αντίστοιχο πρόβλημα απαρίθμησης.

Να σημειωθεί ότι το c_R είναι ένα πρόβλημα αναζήτησης, ενώ το #R είναι ένα πρόβλημα απόφασης. Παρ' όλα αυτά, το c_R μπορεί να αναχθεί κατάCook στο #R με τη χρήση δυαδικής αναζήτησης (ο λόγος που το #R ορίζεται με αυτό τον τρόπο, αντί να αποτελεί απλώς το γράφο του c_R, είναι για να επιτραπεί αυτή ακριβώς η δυαδική αναζήτηση).

Μετρώντας την τάξη πολυπλοκότητας

Αν το NC είναι μια τάξη πολυπλοκότητας που συνδέεται με μη-ντετερμινιστικές μηχανές, τότε το #C = {#R | R ∈ NC} είναι το σύνολο των προβλημάτων απαρίθμησης που σχετίζονται με κάθε πρόβλημα αναζήτησης στο NC. Ειδικότερα, η #P είναι η τάξη των προβλημάτων απαρίθμησης που σχετίζονται με NP προβλήματα αναζήτησης.