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

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

${\displaystyle }$

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

${\displaystyle }$

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

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

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

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