Θεώρημα Κουκ-Λέβιν

Στην θεωρία πολυπλοκότητας το θεώρημα Κουκ-Λέβιν (Cook-Levin), το οποίο επίσης είναι γνωστό ως θεώρημα του Κουκ, αναφέρει ότι το πρόβλημα ικανοποιησιμότητας Boolean  είναι NP-πλήρες.Α υτό σημαίνει ότι οποιοδήποτε πρόβλημα στο NP μπορεί να μειωθεί σε πολυωνυμικό χρόνο από μία ντετερμινιστική μηχανή Turing για το πρόβλημα του καθορισμού αν μία μηχανή Boolean είναι ικανοποιήσιμη.
Το θεώρημα ονομάστηκε από τον Στέφεν Κουκ (Stephen Cook) και τον Λεονίντ Λέβιν (Leonid Levin).
Μία σημαντική συνέπεια του θεωρήματος είναι ότι αν υπήρχε ένας ντετερμινιστικός πολυωνυμικός  αλγοριθμικός χρόνος για την ικανοποιητική λύση του Boolean,τότε θα υπήρχε ένας ντετερμινιστικός  πολυωνυμικός  αλγοριθμικός χρόνος για την λύση όλων των προβλημάτων στο NP. Crucially,το ίδιο ακολουθεί για οποιοδήποτε  NP -πλήρες πρόβλημα.
Το ερώτημα για το αν υπάρχει τέτοιος αλγόριθμος καλείτε P έναντι NP πρόβλημα και θεωρείτε ευρέως το πιο σημαντικό άλυτο πρόβλημα στην επιστημονική θεωρία των υπολογιστών.

Άρθρα

Η έννοια της NP- πληρότητας αναπτύχθηκε στα τέλη της δεκαετίας του 1960 και στις αρχές της δεκαετίας του 1970 παράλληλα με τους ερευνητές στις ΗΠΑ και στην ΕΣΣΔ. Στις ΗΠΑ το 1971, ο Stephen Cook δημοσίευσε το έγγραφό του  "Η πολυπλοκότητα του θεωρήματος θέλει διαδικασίες" σε πρακτικά συνεδριών του νεοσύστατου ACM Συμποσίου για τη θεωρία της πληροφορικής. Το επακόλουθο χαρτί του Richard Karp, "Μειονότητα ανάμεσα σε προβλήματα συνδυαστικής", παράγει ανανεωμένο ενδιαφέρον για το χαρτί του Cook παρέχοντας μια λίστα των 21 NP-πλήρη προβλημάτων. Ο Cook και ο Karp λαμβάνουν ένα βραβείο Turing για το έργο αυτό. 
Το θεωρητικό ενδιαφέρον για την NP-πληρότητα επίσης ενισχύεται από το έργο του Θεώδορου P. Baker, John Gill, and Robert Solovayiπου έδειξαν ότι η επίλυση NP προβλημάτων σε μοντέλα μηχανών Oracle απαιτεί εκθετικό χρόνο. Δηλαδή,υπάρχει ένα oracle A τέτοιο ώστε,για όλες τις subexponential ντετερμινιστικού χρόνου πολυπλοκότητας τάξης T, η σχετικοποιημένη πολυπλοκότητα τάξης NPᴬ δεν είναι ένα υποσύνολο της τάξης Tᴬ. Ειδικότερα, Pᴬ ≠ NPᴬ.
Στην ΕΣΣΔ,ένα ισοδύναμο αποτέλεσμα των Baker, Gill, and Solovay's δημοσιεύτηκε το 1969 από τον M. Dekhtiar. Το χαρτί του Later Levin, "Προβλήματα καθολικής αναζήτησης", δημοσιεύτηκε το 1973, αν και αναφέρθηκε στις συνομιλίες και υποβλήθηκε για δημοσίευση λίγα χρόνια νωρίτερα.
Η προσέγγιση του Levin ήταν μερικώς διαφορετική από του Cook και του Karp από το γεγονός ότι ο ίδιος εξέτασε τα προβλήματα αναζήτησης στα οποία χρειαζόταν εξεύρεση λύσεων παρά απλό προσδιορισμό ύπαρξης. Παρείχε 6 NP-πλήρη προβλήματα αναζήτησης, ή καθολικά προβλήματα. Επιπρόσθετα βρήκε ένα αλγόριθμο για κάθε ένα από αυτά τα προβλήματα ο οποίος το λύνει σε βέλτιστο χρόνο (ιδίως, αυτοί οι αλγόριθμοι τρέχουν σε πολυώνυμο χρόνο αν και μόνο αν P = NP).

Ορισμοί

Ένα πρόβλημα απόφασης ανήκει στο NP αν μπορεί να λυθεί από κάποιο μη ντετερμινιστικό αλγόριθμο σε πολυωνυμικό χρόνο.
Ένα παράδειγμα του προβλήματος ικανοποιησιμότητας Boolean είναι μία λογική έκφραση η οποία περιέχει δυαδικές μεταβλητές και λογικούς τελεστές. 
Μία έκφραση είναι ικανοποιήσιμη αν υπάρχει κάποια ανάθεση αληθοτιμών η οποία καθιστά ολόκληρη την έκφραση αληθή.

Ιδέα

Δίνεται κάποιο πρόβλημα απόφασης σε NP,που κατασκευάζει μία μη ντετερμινιστική μηχανή η οποία λύνει σε πολυωνυμικό χρόνο. Έπειτα για κάθε εισαγόμενο κομμάτι σε αυτή τη μηχανή, χτίζουμε μια έκφραση Boolean η οποία λέει ότι το εισαγόμενο κομμάτι περνιέται στη μηχανή, η μηχανή τρέχει σωστά, και η μηχανή σταματάει και απαντάει "ναι". Έπειτα η έκφραση μπορεί να είναι ικανοποιητική αν και μόνο αν υπάρχει ένας τρόπος να τρέξει σωστά η μηχανή και να απαντήσει "ναι", έτσι ώστε η ικανοποίηση από την κατασκευαστική έκφραση να είναι ισοδύναμη με την ερώτηση αν η μηχανή θα απαντήσει "ναι".

Συνέπειες

Η απόδειξη δείχνει ότι οποιοδήποτε πρόβλημα σε NP μπορούν να μειωθούν σε πολυώνυμο χρόνο σε μια παρουσία του προβλήματος ικανοποιησιμότητας Boolean. Αυτό σημαίνει ότι αν το πρόβλημα ικανοποιησιμότητας Boolean θα μπορούσε να λυθεί σε πολυωνυμικό χρόνο από μία ντετερμινιστική μηχανή Turing , τότε όλα τα προβλήματα NP θα μπορούσαν να λυθούν σε πολυωνυμικό χρόνο, έτσι και η κλάση πολυπλοκότητας  NP θα ήταν ίση με την κλάση πολυπλοκότητας P.
Η σημασία της NP-πληρότητας έγινε καθαρά από δημοσίευση το 1972 από ορόσημο χαρτί του Richard Karp, "Μειονότητα μέσω προβλημάτων συνδυαστικής", στα οποία έδειξε ότι 21 διαφορετικές συνδυαστικές και γραφικά θεωρητικά προβλήματα, το καθένα κακόφημο για την intractability του, είναι NP-πλήρες.
Ο Garey και ο Johnson παρουσίασαν πάνω από 300 NP-πλήρη προβλήματα στο βιβλίο τους Υπολογιστές και Intractability: Ένας οδηγός στη θεωρία της NP-πληρότητας,[6] και νέα προβλήματα που εξακολουθούν να ανακαλύπτονται εντός αυτής της τάξης πολυπλοκότητας.
Παρόλα αυτά πολλά πρακτικά παραδείγματα του SAT μπορούν να λυθούν με εριστικές μεθόδους, παρά τις δεκαετίες έντονης προσπάθειας από τους θεωρητικούς της πολυπλοκότητας, καθηγητές μαθηματικών λογικών, και άλλους.