Θεωρία υπολογισμού: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μΧωρίς σύνοψη επεξεργασίας |
μ →Βιβλιογραφία: αφαίρεση, το βιβλίο που έχει προστεθεί δεν προϋπήρχε στην Βιβλιογραφία σύμφ. με το ιστορικό |
||
Γραμμή 63:
Τα προβλήματα του NP που δεν φαίνεται να ανήκουν στο P έχουν την ιδιότητα να ανάγονται όλα σε ένα μικρό σύνολο βασικών και καλά μελετημένων προβλημάτων. Αυτή η ιδιότητα ονομάζεται ''πληρότητα'' και τα εν λόγω προβλήματα ονομάζονται ''NP-πλήρη''. Έχει αποδειχθεί ότι αν ανακαλυφθεί κάποτε Μηχανή Τούρινγκ που να επιλύει κάποιο από αυτά ντετερμινιστικά σε πολυωνυμικό χρόνο (οπότε αυτό θα ανήκει στο P), τότε όλα τα NP-πλήρη προβλήματα θα ανήκουν στο P. Όπως προαναφέρθηκε ωστόσο αυτό δεν θεωρείται πιθανό.
{{Μαθηματικά-υποσέλιδο}}
| |||