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

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

$c_R(x)=|\{y\mid R(x,y)\}|$

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

$\mathrm{\#}R=\{(x,y)\mid y\le c_R(x)\}$

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

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

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

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