36 

 

από  τους  αλγορίθμους  ασφαλείας  βασίζονται  στο  γεγονός  ότι  δεν  υπάρχει  παράκαμψη  στις 

υπολογιστικές απαιτήσεις των προβλημάτων NP [Εικόνα 2.13b]. 

 

Εικόνα 2.13: Κλάσεις Πολυπλοκότητας (a) P≠NP (b) P=NP.

 

 

2.4.1 Κλάση NP 

Η κλάση NP περιέχει προβλήματα απόφασης που λύνονται σε πολυωνυμικό χρόνο με 

μία μη-ντετερμινιστική μηχανή Turing [53]. Αν και η επίλυση τους μπορεί να απαιτήσει πολύ 

χρόνο,  μπορεί  να  επαληθευτεί  αν  η  λύση  είναι  σωστή  από  μία  μηχανή  Turing  σε 

πολυωνυμικό  χρόνο.  Η  επαλήθευση  αυτή  ονομάζεται  "μάρτυρας"  ή  "πιστοποίηση"  της 

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

Υποσύνολο  της  κλάσης  NP  είναι  η  κλάση  P  (P⊂NP)  [Εικόνα  2.13a].  Γνωστά  προβλήματα 

κλάσης  NP  είναι:  ο  ισομορφισμός  και  χρωματισμός  γράφων  [54],  το  πρόβλημα  πλανόδιου 

πωλητή [55], η παραγοντοποίηση ακεραίων [56], SAT [57]. 

 

2.4.2 Κλάση P 

Η  κλάση  P  περιέχει  προβλήματα  απόφασης  (προβλήματα  που  μπορούν  να 

απαντηθούν  με  ναι  ή  όχι)  που  λύνονται  σε  πολυωνυμικό  χρόνο  με  μία  ντετερμινιστική 

μηχανή  Turing  [53].  Πολλά  από  τα  προβλήματα  της  λύνονται  με  προσεγγίσεις  brute-force 

(χρήση  υπολογιστικής  δύναμης  δοκιμάζοντας  κάθε  πιθανό  συνδυασμό  για  εύρεση  λύσης) 

αλλά  συχνά  απαιτούν  εκθετικό  χρόνο.  Φυσικά  αν  το  πρόβλημα  διαθέτει  αλγόριθμο 

πολυωνυμικού χρόνου μπορεί να λυθεί πολύ πιο αποδοτικά. Ένα πρόβλημα κλάσης P λύνεται 

σε n

k

 χρόνο όπου k είναι σταθερά και n το μέγεθος της εισόδου [53]. Επιπρόσθετη βελτίωση 

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