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

Στην θεωρία πολυπλοκότητας το θεώρημα Κουκ-Λέβιν (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, "Μειονότητα ανάμεσα σε προβλήματα συνδυαστικής",^[1] παράγει ανανεωμένο ενδιαφέρον για το χαρτί του Cook παρέχοντας μια λίστα των 21 NP-πλήρη προβλημάτων. Ο Cook και ο Karp λαμβάνουν ένα βραβείο Turing για το έργο αυτό.

Το θεωρητικό ενδιαφέρον για την NP-πληρότητα επίσης ενισχύεται από το έργο του Θεώδορου P. Baker, John Gill, and Robert Solovayiπου έδειξαν ότι η επίλυση NP προβλημάτων σε μοντέλα μηχανών Oracle απαιτεί εκθετικό χρόνο. Δηλαδή,υπάρχει ένα oracle A τέτοιο ώστε,για όλες τις subexponential ντετερμινιστικού χρόνου πολυπλοκότητας τάξης T, η σχετικοποιημένη πολυπλοκότητα τάξης NP^A δεν είναι ένα υποσύνολο της τάξης T^A. Ειδικότερα, P^A ≠ NP^A.^[2]

Στην ΕΣΣΔ,ένα ισοδύναμο αποτέλεσμα των Baker, Gill, and Solovay's δημοσιεύτηκε το 1969 από τον M. Dekhtiar^[3]. Το χαρτί του Later Levin, "Προβλήματα καθολικής αναζήτησης"^[4], δημοσιεύτηκε το 1973, αν και αναφέρθηκε στις συνομιλίες και υποβλήθηκε για δημοσίευση λίγα χρόνια νωρίτερα.

Η προσέγγιση του Levin ήταν μερικώς διαφορετική από του Cook και του Karp από το γεγονός ότι ο ίδιος εξέτασε τα προβλήματα αναζήτησης στα οποία χρειαζόταν εξεύρεση λύσεων παρά απλό προσδιορισμό ύπαρξης. Παρείχε 6 NP-πλήρη προβλήματα αναζήτησης, ή καθολικά προβλήματα. Επιπρόσθετα βρήκε ένα αλγόριθμο για κάθε ένα από αυτά τα προβλήματα ο οποίος το λύνει σε βέλτιστο χρόνο (ιδίως, αυτοί οι αλγόριθμοι τρέχουν σε πολυώνυμο χρόνο αν και μόνο αν P = NP).

Ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

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

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

Μία έκφραση είναι ικανοποιήσιμη αν υπάρχει κάποια ανάθεση αληθοτιμών η οποία καθιστά ολόκληρη την έκφραση αληθή.

Ιδέα[Επεξεργασία | επεξεργασία κώδικα]

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

Απόδειξη[Επεξεργασία | επεξεργασία κώδικα]

Η απόδειξη αυτή είναι βασισμένη σε αυτήν που έχει δοθεί από τους Garey και Johnson.^[5]

Υπάρχουν 2 μέρη για να αποδείξεις ότι το πρόβλημα ικανοποιησιμότητας Boolean (SAT) είναι NP-πλήρες. Το ένα είναι να δείξεις ότι το SAT είναι ένα NP πρόβλημα.Το άλλο είναι να δείξεις ότι κάθε NP πρόβλημα μπορεί να μειωθεί σε ένα παράδειγμα του προβλήματος SAT από ένα πολυωνυμικού χρόνου πολλά σε ένα μείωση.

Το SAT είναι NP επειδή οποιαδήποτε ανάθεση των τιμών Boolean σε μεταβλητές Boolean που ισχυρίζεται να ικανοποιήσει την δοσμένη έκφραση μπορεί να επαληθευτεί σε πολυωνυμικό χρόνο από μια ντετερμινιστική μηχανή Turing. (Οι βεβαιώσιμες δηλώσεις σε πολυωνoμικό χρόνο από μια ντετερμινιστική μηχανή Turing και λυμένες σε πολυωνoμικό χρόνο από μια μη ντετερμινιστική μηχανή Turing είναι εντελώς ισοδύναμες, και η απόδειξη μπορεί να βρεθεί σε πολλά εγχειρίδια,για παράδειγμα εισαγωγή του Sipser στην υπολογιστική θεωρία,παράγραφος 7.3.).

Τώρα υπέθεσε ότι ένα δοσμένο πρόβλημα στο NP μπορεί να λυθεί από μία μη ντετερμινιστική μηχανή Turing M = (Q,Σ,s,F,δ), όπου Q είναι το σύνολο των καταστάσεων, Σ είναι το αλφάβητο των συμβόλων ταινίας, s ∈ Q είναι η αρχική κατάσταση, F ⊆ Q είναι το σύνολο των καταστάσεων υποδοχής, και δ ⊆ ((Q\F) x Σ) x (Q x Σ x {-1, +1}) η σχέση μετάβασης.

Για κάθε εισαγωγή, I , εμείς προσδιορίζουμε μια έκφραση Boolean η οποία είναι ικανοποιητική αν και μόνο αν η μηχανή M δέχεται την Ι.

Η έκφραση Boolean χρησιμοποιεί τις μεταβλητές που ορίζονται στον ακόλουθο πίνακα. Εδώ, q ∈ Q, -p(n) ≤ i ≤p(n, j ∈ Σ, και 0≤ k ≤ p(n).

Μεταβλητές	Προβλεπόμενη διερμηνεία	Πόσα;
T_i,j,k	Αληθές αν το κελί i περιέχει το σύμβολο j στο βήμα k του υπολογισμού.	O(p(n)²)
H_i,k	Αληθές αν η κεφαλή ανάγνωσης/γραψίματος του Μ είναι στο κελί i στο βήμα k του υπολογισμού.	O(p(n)²)
Q_q,k	Αληθές αν το M είναι στην κατάσταση q στο βήμα k του υπολογισμού.	O(p(n))

Ορίστε η έκφραση Boolean B ως συνδυασμός των επί μέρους εκφράσεων στον παρακάτω πίνακα, για όλα τα −p(n) ≤ i ≤ p(n) και 0 ≤ k ≤ p(n):

Έκφραση	Συθήκες	Διερμηνεία	Πόσα;
T_i,j,0	Το κελί i αρχικά περιλαμβάνει το σύμβολο j	Αρχικά περιεχόμενα της ταινίας. Για i > n-1 και i < 0, έξω από την πραγματική είσοδο I, το αρχικό σύμβολο είναι το ειδικό κενό σύμβολο.	O(p(n))
Q_s,0		Αρχική κατάσταση του M.	1
H_0,0		Αρχική θέση της κεφαλής ανάγνωσης/γραψίματος.	1
¬T_i,j,k ∨ ¬T_i,j′,k	j ≠ j′	Το πολύ ένα σύμβολο ανά κελί.	O(p(n)²)
_j ∈ Σ T_i_,j,k		Τουλάχιστον ένα σύμβολο ανά κελί.	O(p(n)²)
T_i,j,k ∧ T_i,j′_,k+1 → H_i,k	j ≠ j′	Το κελί παραμένει αμετάβλητο εκτός αν έχει εγγραφή.	O(p(n)²)
¬Q_q,k ∨ ¬Q_q′,k	q ≠ q′	Μόνο μία κατάσταση τη φορά.	O(p(n))
¬H_i,k ∨ ¬H_i′,k	i ≠ i′	Μόνο μία θέση κεφαλής τη φορά.	O(p(n)³)
(H_i,k ∧ Q_q,k ∧ T_i,σ,k) → _{(q, σ, q′, σ′, d) ∈ δ}(H_i_+d,k+1 ∧ Q_q′_,k+1∧ T_i,σ′_,k+1)	k<p(n)	Πιθανή μετάβαση του υπολογισμού στο βήμα k όταν η κεφαλή είναι στη θέση i.	O(p(n)²)
_0≤k≤p(n) _f ∈ F Q_f_,k		Πρέπει να τελειώσει σε μία αποδεκτή κατάσταση, όχι πιο μετά από το βήμα p(n).	1

Αν υπάρχει μία αποδοχή υπολογισμού για το M στην είσοδο I, τότε το B είναι ικανοποιήσιμο θέτοντας T_i,j,k, H_i,k και Q_i,k ως ερμηνείες προορισμού τους. Από την άλλη πλευρά, αν το B είναι ικανοποιήσιμο, τότε υπάρχει μία αποδοχή υπολογισμού για το M στην είσοδο I η οποία ακολουθεί τα βήματα που υποδεικνύονται από τις εργασίες με τις μεταβλητές.

Υπάρχουν O(p(n)²) μεταβλητές Boolean, κάθε μία κωδικοποιημένη στο διάστημα O(log p(n)). Ο αριθμός των ρητών είναι O(p(n)³) έτσι το μέγεθος του B είναι O(log(p(n))p(n)³).Έτσι η μετατροπή είναι σίγουρα πολυωνυμικού χρόνου πολλά σε ένα, όπως απαιτείται.

Συνέπειες[Επεξεργασία | επεξεργασία κώδικα]

Η απόδειξη δείχνει ότι οποιοδήποτε πρόβλημα σε NP μπορούν να μειωθούν σε πολυώνυμο χρόνο σε μια παρουσία του προβλήματος ικανοποιησιμότητας Boolean. Αυτό σημαίνει ότι αν το πρόβλημα ικανοποιησιμότητας Boolean θα μπορούσε να λυθεί σε πολυωνυμικό χρόνο από μία ντετερμινιστική μηχανή Turing , τότε όλα τα προβλήματα NP θα μπορούσαν να λυθούν σε πολυωνυμικό χρόνο, έτσι και η κλάση πολυπλοκότητας NP θα ήταν ίση με την κλάση πολυπλοκότητας P.

Η σημασία της NP-πληρότητας έγινε καθαρά από δημοσίευση το 1972 από ορόσημο χαρτί του Richard Karp, "Μειονότητα μέσω προβλημάτων συνδυαστικής", στα οποία έδειξε ότι 21 διαφορετικές συνδυαστικές και γραφικά θεωρητικά προβλήματα, το καθένα κακόφημο για την intractability του, είναι NP-πλήρες.

Ο Garey και ο Johnson παρουσίασαν πάνω από 300 NP-πλήρη προβλήματα στο βιβλίο τους Υπολογιστές και Intractability: Ένας οδηγός στη θεωρία της NP-πληρότητας,[6] και νέα προβλήματα που εξακολουθούν να ανακαλύπτονται εντός αυτής της τάξης πολυπλοκότητας.

Παρόλα αυτά πολλά πρακτικά παραδείγματα του SAT μπορούν να λυθούν με εριστικές μεθόδους, παρά τις δεκαετίες έντονης προσπάθειας από τους θεωρητικούς της πολυπλοκότητας, καθηγητές μαθηματικών λογικών, και άλλους.

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ Karp, Richard M. (1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller and James W. Thatcher (editors). Complexity of Computer Computations (PDF). New York: Plenum. pp. 85–103. ISBN 0-306-30707-3.
↑ T. P. Baker; J. Gill; R. Solovay (1975). "Relativizations of the P = NP question". SIAM Journal on Computing 4 (4): 431–442. doi:10.1137/0204037.
↑ Dekhtiar, M. (1969). "On the impossibility of eliminating exhaustive search in computing a function relative to its graph". Proceedings of the USSR Academy of Sciences (in Russian) 14: 1146–1148.
↑ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) 9 (3): 115–116. (pdf) (Russian), translated into English by Trakhtenbrot, B. A. (1984). "A survey of Russian approaches to perebor (brute-force searches) algorithms". Annals of the History of Computing 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.
↑ Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

[1] Karp, Richard M. (1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller and James W. Thatcher (editors). Complexity of Computer Computations (PDF). New York: Plenum. pp. 85–103. ISBN 0-306-30707-3.

[2] T. P. Baker; J. Gill; R. Solovay (1975). "Relativizations of the P = NP question". SIAM Journal on Computing 4 (4): 431–442. doi:10.1137/0204037.

[3] Dekhtiar, M. (1969). "On the impossibility of eliminating exhaustive search in computing a function relative to its graph". Proceedings of the USSR Academy of Sciences (in Russian) 14: 1146–1148.

[4] Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii) 9 (3): 115–116. (pdf) (Russian), translated into English by Trakhtenbrot, B. A. (1984). "A survey of Russian approaches to perebor (brute-force searches) algorithms". Annals of the History of Computing 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.

[5] Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

[1]

[2]

[3]

[4]

[5]