Στις εικόνες 2 και 3 παρουσιάζονται η εικόνα του παιχνιδιού (όπως φαίνεται στον υπολογιστή) και η τυπική διάταξή του ύστερα από μερικές κινήσεις,αντίστοιχα. <---(Εικόνα 2η) (εικόνα 3η)---------->

Για να δούμε όμως πώς συνδέεται ο Ναρκαλιευτής με ένα μαθηματικό πρόβλημα.
Το πρόβλημα είναι γνωστό ως πρόβλημα Ρ vs ΝΡ. Το ζητούμενο είναι μια διαδικασία που να μπορεί να ΄΄τρέξει΄΄ στον υπολογιστή και να δώσει λύση στο πρόβλημα. Πολύ σημαντικότερο όμως είναι ο αριθμός των υπολογισμών που απαιτούνται για να δοθεί μια πλήρης απάντηση.

Το παραπάνω είναι αυτό που χωρίζει τα προβλήματα τέτοιου είδους σε Ρ και μη-Ρ. Ένα πρόβλημα είναι Ρ όταν λύνεται με κάποιον αλγόριθμο που ο χρόνος λειτουργίας του δεν αυξάνεται γρηγορότερα από μια καθορισμένη δύναμη του αριθμού των συμβόλων των αρχικών δεδομένων. Στην αντίθετη πεπρίπτωση το πρόβλημα είναι μη-Ρ.

Η δυσκολία έγκειται στο ότι ο υπολογιστής μπορεί να διαχειρισθεί ένα πρόβλημα μόνο όταν αυτό είναι τύπου Ρ. Τα μη-Ρ προβλήματα, αντίθετα δεν μπορούν να αντιμετωπισθούν από έναν υπολογιστή γιατί θα χρειασθεί υπερβολικά μεγάλο χρονικό διάστημα για να δοθεί μια απάντηση.

Το βασικό είναι να αποδειχθεί σε ποιο είδος ανήκει ένα τέτοιο πρόβλημα. Εάν βρεθεί ένας αλγόριθμος που να λύνει το πρόβλημα σε πολυωνυμικό χρόνο, τότε αυτό είναι τύπου Ρ. Για παράδειγμα Ρ πρόβλημα είναι η κατάταξη των αριθμών από το μικρότερο στον μεγαλύτερο και αντίστροφα (ήδη επιτυγχάνεται από υπολογιστές που χειρίζονται βάσεις δεδομένων). Αντίθετα, ευρέως διαδεδομένα μη-Ρ προβλήματα (αν και κάτι τέτοιο δεν έχει αποδειχθεί), θεωρούνται η εύρεση της μικρότερης διαδρομής που πρέπει να ακολουθήσει ένας ταχυδρόμος για να περάσει από όλες τις πόλεις με κάποιο δρομολόγιο και η εύρεση των πρώτων διαιρεταίων ενός δεδομένου ακεραίου.

Γιατί όμως δεν είναι εύκολο να λυθεί ένα μη-Ρ πρόβλημα; Προφανώς γιατί για να λυθεί πρέπει να συλλογιστεί κανείς όλους τους πιθανούς αλγόριθμους, κάτι που είναι πολύ δύσκολο. Έως τώρα το μόνο που έχει αποδειχθεί είναι ότι ένα μεγάλο μέρος από μη-Ρ προβλήματα έχουν την ίδια βάση. Αν κάποιο λύνεται σε πολυωνυμικό χρόνο,τότε και όλα τ'άλλα μπορούν να λυθούν έτσι. Τέτοια προβλήματα ονομάζονται ΝΡ.

Τα ΝΡ διαφέρουν από τα μη-Ρ ως προς το γεγονός ότι κάποιος μπορεί να ελέγξει στα πρώτα αν μια προτεινόμενη λύση είναι σωστή σε πολυωνυμικό χρόνο. Σπουδαίο παράδειγμα ΝΡ προβλήματος είναι τα puzzle. Ο χρόνος ΄΄λύσης΄΄ ενός puzzle είναι τεράστιος όμως εάν κάποιος καταφέρει να το συναρμολογίσει, τότε εύκολα κάποιος άλλος μπορεί να ελέγξει εάν έχει συναρμολογηθεί σωστά. Αν η εύρεστη ενός πολυωνυμικού χρόνου λύσης για ένα ΝΡ πρόβλημα συνεπάγεται την λύση όλων των ΝΡ προβλημάτων, τότε το πρόβλημα αυτό ονομάζεται ΝΡ -πλήρες. 

Ας επιστρέψουμε όμως στον Ναρκαλιευτή. Το πρόβλημα ουσιαστικά δεν έγκειται στην ανακάλυψη των ναρκών αλλά στον έλεγχο της συνέπειας μίας δεδομένης θέσης.  Εάν, δηλαδή, συναντούσε κανείς τη διάταξη του σχήματος 3 θα νόμιζε ότι ο προγραμματιστής έχει κάνει λάθος αφού οι θέσεις των ναρκών δεν θα ήταν συνεπείς με τα νούμερα στα τετράγωνα. Το βασικό λοιπόν είναι ότι εάν λυθεί το πρόβλημα του Ναρκαλιευτή σε πολυωνυμικό χρόνο τότε θα έχουν λυθεί όλα τα ΝΡ προβλήματα αφού και ο Ναρκαλιευτής είναι ΝΡ-πλήρης.

Ωστόσο το πρόβλημα συνέπειας του Ναρκαλιευτή είναι πάρα πολύ δύσκολο. Λίγοι βέβαια είναι εκείνοι που πιστεύουν ότι υπάρχει λύση του παραπάνω προβλήματος, η οποία να ΄΄τρέχει΄΄ σε πολυωνυμικό χρόνο.