Πρόβλημα απαρίθμησης: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Δημιουργήθηκε από μετάφραση της σελίδας "Counting problem (complexity)" |
μ math και επ. |
||
Γραμμή 1:
Στη [[Θεωρία πολυπλοκότητας|θεωρία υπολογιστικής πολυπλοκότητας]] και τη [[θεωρία υπολογισιμότητας]], ένα '''πρόβλημα απαρίθμησης''' είναι ένα είδος [[Υπολογιστικό πρόβλημα|υπολογιστικού προβλήματος]]. Έστω ότι το ''R'' είναι ένα [[πρόβλημα αναζήτησης]]. Τότε το
:<math>c_R(x)=\vert\{y\mid R(x,y)\}\vert \,</math>
είναι η αντίστοιχη [[συνάρτηση απαρίθμησης]] και το
:<math>\#R=\{(x,y)\mid y\leq c_R(x)\}</math>
υποδηλώνει το αντίστοιχο πρόβλημα απαρίθμησης.
== Μετρώντας την τάξη πολυπλοκότητας ==
Αν το ''NC'' είναι μια τάξη πολυπλοκότητας που συνδέεται με [[Μη-ντετερμινιστικός αλγόριθμος|μη-ντετερμινιστικές]] μηχανές, τότε το ''#C'' = {''#R'' | ''R'' ∈ ''NC''} είναι το σύνολο των προβλημάτων απαρίθμησης που σχετίζονται με κάθε [[πρόβλημα αναζήτησης]] στο ''NC''. Ειδικότερα, η #P είναι η τάξη των προβλημάτων απαρίθμησης που σχετίζονται με NP προβλήματα αναζήτησης.
| |||