20 

 

 

Τα αποτελέσματα του Kaye έκαναν ιδιαίτερα γνωστό ένα από τα μεγαλύτερα ανοικτά 

προβλήματα στα σύγχρονα μαθηματικά, το P vs NP [11]. Το πρόβλημα αυτό ανήκει στα επτά 

προβλήματα του βραβείου Μιλλένιουμ από το Ινστιτούτο Μαθηματικών Κλέι με αμοιβή ένα 

εκατομμύριο  δολάρια  για  την  πρώτη  λύση.  Το  2002  ο  ίδιος  απέδειξε  ότι  ο  Ναρκαλιευτής 

είναι Turing-complete το οποίο σημαίνει πως στα πλαίσια του παιχνιδιού μπορεί να γραφτεί 

ένα πρόγραμμα που πάντα θα δώσει λύση ωστόσο δίχως εγγυήσεις για το χρόνο ή τη μνήμη 

που θα απαιτηθεί [12]. 

 

Το 2004, ο Pedersen συνεισέφερε στη μελέτη του Ναρκαλιευτή κάνοντας αποδείξεις 

στα πλαίσια των κλάσεων προβλημάτων πολυπλοκότητας  DP και #P [13]. Εξηγεί ότι το να 

διαπιστώσουμε αν ένα ταμπλό έχει μοναδική λύση, όπως και το να ελέγξουμε αν μία κίνηση 

είναι  ασφαλής  είναι  DP-complete  προβλήματα  χωρίς  ανάγκη  για  ένα  ταμπλό  που  τηρεί  τη 

συνοχή  στα  πρότυπα  του  Kaye.  Ταυτόχρονα,  εισάγει  το  Πρόβλημα  Καταμέτρησης  κατά  το 

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

Συνοχή κατά Kaye και αποδεικνύει ότι είναι #P-complete. 

 

Το 2012, ο de Bondt έδωσε μια νέα ματιά στο πρόβλημα Συνοχής του Ναρκαλιευτή 

τεκμηριώνοντας  ότι  είναι  κι  αυτό  NP-complete  για  τετράγωνα  ταμπλό  (n×n)  με  την 

προϋπόθεση  πως  η  αρχική  κίνηση  αποκαλύπτει  μόνο  ένα  μπλοκ  [14].  Επιπρόσθετα,  έκανε 

ανάλυση της πολυπλοκότητας της διαδικασίας του παιχνιδιού δεδομένου ότι σε κάθε κίνηση 

οι  εναπομένουσες  διαμορφώσεις  των  ναρκών  που  τηρούν  τη  Συνοχή  κατά  Kaye  είναι 

ισοπίθανες. 

 

1.3.2 Αλγόριθμοι και Επιλυτές 

 

Η  μελέτη  των  πιθανών  στρατηγικών,  αλλά  και  η  προγραμματιστική  πρόκληση  που 

παρουσιάστηκε  με  την  κυκλοφορία  του  Ναρκαλιευτή  είχε  ως  αποτέλεσμα  διαφορετικές 

προσεγγίσεις  ανά  τα  χρόνια.  Οι  προσεγγίσεις  είτε  είχαν  ως  σκοπό  το  μεγαλύτερο  ποσοστό 

επιτυχίας,  είτε  να  προσδώσουν  μία  ολοκαίνουργια  ματιά  συμπληρώνοντας  προϋπάρχοντα 

έργα.  Οι  επικρατέστεροι  αλγόριθμοι  θα  εξεταστούν  με  μεγαλύτερη  λεπτομέρεια  στο 

Κεφάλαιο 3. 

 Μία από τις πρώτες υλοποιήσεις έκανε ο Adamatzky [15] το 1997 με τη μορφή ενός 

διακριτού  υπολογιστικού  μοντέλου  που  ονομάζεται  Κυτταρικό  Αυτόματο.  Καινοτόμες 

προσεγγίσεις  είχαν  ο  Kamenetsky  [16]  και  ο  Golan  [17]  με  γραφικά  μοντέλα,  ο  Nakov  με