37
σταθερές [58]. Γνωστά προβλήματα κλάσης P είναι: ο γραμμικός προγραμματισμός [59], ο
έλεγχος πρώτων αριθμός [60], η σύγκριση συμβολοσειρών, το ελάχιστο επικαλύπτων δένδρο.
2.4.3 Κλάση NP-Complete
Τα προβλήματα NP-Complete είναι ένα υποσύνολο προβλημάτων στα οποία μπορεί να
αναχθεί σε πολυωνυμικό χρόνο καθένα από τα προβλήματα της NP και η λύση των οποίων
μπορεί να επαληθευτεί σε επίσης πολυωνυμικό χρόνο [61]. Ως αποτέλεσμα του ορισμού, αν
υπήρχε ένας αλγόριθμος πολυωνυμικού χρόνου για τη λύση NP-Complete προβλημάτων θα
μπορούσε να λυθεί κάθε πρόβλημα της NP σε ανάλογο χρόνο. Το θεώρημα Cook-Levin
δείχνει με τη μέθοδο απόδειξης δια αναγωγής πως τα Προβλήματα Ικανοποίησης Boolean
ανήκουν στην κλάση NP-Complete [62].
Εκατοντάδες προβλήματα έχουν διατυπωθεί και εισαχθεί στην εκτενή λίστα της
κλάσης NP-Complete. Σε τομείς όπως οι γράφοι, ο μαθηματικός προγραμματισμός, η
ανάλυση κειμένου και συμβολοσειρών αλλά και στα παιχνίδια συναντώνται και εκφράζονται
τέτοια προβλήματα. Μερικά γνωστά παραδείγματα αποτελούν: το πρόβλημα σακιδίου [63], ο
προγραμματισμός ακεραίων, ο ισομορφισμός γράφων [54], ο χρωματισμός γράφων [64], το
πρόβλημα μονοπατιού Hamilton [65] και η δρομολόγηση οχημάτων.
2.5 Μοντέλα Προβλημάτων
Κάνοντας αναγωγή του προβλήματος σε κυκλωματικό SAT ο Kaye απέδειξε πως ο
Ναρκαλιευτής ανήκει στα προβλήματα NP-Complete [10]. Ορισμένες σύνθετες καταστάσεις
του Ναρκαλιευτή μπορούν να διατυπωθούν ως μοντέλα CSP και να κωδικοποιηθούν σε
μορφή Boolean. Αυτό επιτρέπει να λυθούν με εργαλεία που κάνουν συνδυασμό SAT και
προγραμματισμού περιορισμών. Είναι κρίσιμο να αναλυθούν τα δύο μοντέλα προβλημάτων
ώστε να μπορεί να περιγραφεί η διαδικασία.
2.5.1 CSP
Ως Προβλήματα Ικανοποίησης Περιορισμών (CSP) ορίζονται τα προβλήματα που η
επίλυση τους περιλαμβάνει την ανάθεση κατάλληλων τιμών στις μεταβλητές τους ώστε να
ικανοποιούν ορισμένους περιορισμούς ή κανόνες [66]. Συνήθως είναι απαραίτητη η χρήση
ευριστικών μεθόδων και αλγόριθμων συνδυαστικής αναζήτησης για την επίλυσή τους σε