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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

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

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

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

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

Μετρώντας την τάξη πολυπλοκότητας[Επεξεργασία | επεξεργασία κώδικα]

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