19 

 

διεκπεραίωση  πειραματικής  διαδικασίας  τα  αποτελέσματα  της  οποίας  θα  εξεταστούν  στο 

Κεφάλαιο 4. 

 

1.3 Σχετικές Εργασίες 

 

Ο Ναρκαλιευτής έχει τις ρίζες του στη δεκαετία του εξήντα, αλλά κυκλοφόρησε για 

υπολογιστή  το  1989.  Δεν  άργησε  να  εγείρει  το  ενδιαφέρον  επιστημονικών  κοινοτήτων 

επιφέροντας  επιφανείς  μελέτες  και  αλγοριθμικές  προσεγγίσεις  για  την  επίλυσή  του  με  τις 

πρώτες  δημοσιεύσεις  να  εμφανίζονται  τη  δεκαετία  του  ενενήντα.  Στις  δημοσιεύσεις  αυτές 

θεμελιώθηκαν αποδείξεις για το παιχνίδι, ενώ ανά τα χρόνια σημειώθηκε σημαντική πρόοδος 

όσον αφορά τις στρατηγικές επίλυσης.  

1.3.1 Θεωρητική Μελέτη 

 

Ο  Richard  Kaye  έγινε  πρωτοπόρος  το  2000  φέρνοντας  στο  προσκήνιο  το  λεγόμενο 

πρόβλημα Συνοχής του Ναρκαλιευτή (ή απλά Συνοχής) μαζί με αποδείξεις πως ανήκει στην 

κλάση προβλημάτων πολυπλοκότητας NP-complete [10]. Κατά το πρόβλημα Συνοχής, πρέπει 

να  βρεθεί  αν,  για  ένα  μερικώς  αποκαλυμμένο  ταμπλό,  υπάρχει  τρόπος  τοποθέτησης  των 

εναπομεινάντων  ναρκών  που  να  έχει  συνοχή  με  την  κατάσταση  του  ταμπλό.  Σε  αυτό  το 

σημείο, επειδή η επιβεβαίωση του τρόπου τοποθέτησης απαιτεί πολυωνυμικό χρόνο, έχει ήδη 

αποδείξει ότι ανήκει στην κλάση NP. Στη συνέχεια, έδειξε πως διάφορες διαμορφώσεις του 

ταμπλό  μιμούνται  τη  συμπεριφορά  καλωδίου  ή  διανεμητή  (splitter)  καθώς  και  ορισμένες 

λογικές πύλες [Εικόνα 1.2]. Δείχνοντας πως αυτές οι καταστάσεις μπορούν να συνδυαστούν 

με  οποιοδήποτε  τρόπο  για  να  φτιάξουν  κάθε  λογικό  κύκλωμα  τεκμηρίωσε  πως  μπορεί  να 

γίνει αναγωγή του προβλήματος σε κύκλωμα SAT κάτι το οποίο επιλύεται σε πολυωνυμικό 

χρόνο άρα είναι και NP-complete.  

 

Εικόνα 1.2 Αναπαράσταση Καλωδίου κατά τα πρότυπα του Kaye.