38 

 

λογικό χρόνο καθώς τα CSP παρουσιάζουν μεγάλη χρονική πολυπλοκότητα. Με την εξαγωγή 

εφικτών  λύσεων  και  τη  βελτίωση  των  μεθόδων  αυτών  ασχολείται  ο  κλάδος  του 

προγραμματισμού  περιορισμών.  Κατά  την  εργασία  "A  dichotomy  theorem  for  nonuniform 

CSPs" [67], αποδεικνύεται πως ένα πεπερασμένο σύνολο προβλημάτων CSP λύνονται είτε σε 

πολυωνυμικό χρόνο (κλάσης P) είτε είναι NP-Complete. 

Τα μοντέλα CSP ορίζονται με τρία βασικά κομμάτια 〈𝑋, 𝐷, 𝐶〉: 

• 

Σύνολο μεταβλητών 𝑋 = {𝑋1, 𝑋2, . . . , 𝑋𝑁}   

 

(2.7)

 

•  Σύνολο πεδίων ορισμού τιμών 𝐷 = {𝐷1, 𝐷2, . . . , 𝐷𝑁} 

(2.8)

 

•  Σύνολο Περιορισμών 𝐶 = {𝐶1, 𝐶2, . . . , 𝐶𝑁}   

 

(2.9)

 

Σε  κάθε  μεταβλητή  X

i

  ανατίθεται  ένα  πεδίο  ορισμού  D

i

  που  δεν  είναι  κενό  για  να 

πάρει τις τιμές της. Κάθε περιορισμός C

i

 μπορεί να περιέχει οποιοδήποτε αριθμό μεταβλητών 

και παίρνει τιμές αληθές ή ψευδές αναλόγως με το αν ικανοποιείται. 

𝐶

𝑘

:  𝑝𝑜𝑤𝑒𝑟𝑠𝑒𝑡(𝐷) → {𝑡𝑟𝑢𝑒, 𝑓𝑎𝑙𝑠𝑒}, 𝑘 = 1,2, … 𝑚  

(2.10)

 

➢  Η ανάθεση είναι συνεπής αν τηρούνται όλοι οι περιορισμοί C. 

➢  Η ανάθεση είναι πλήρης αν κάνει χρήση όλων των μεταβλητών X. 

➢  Οι αναθέσεις μπορούν να είναι μερικές αν χρησιμοποιούν υποσύνολο της Χ. 

➢  Μία  ανάθεση  αποτελεί  λύση  του  προβλήματος  ικανοποίησης  περιορισμών  αν  είναι 

συνεπής και πλήρης.  

Διάδοση Περιορισμών 

Τα μοντέλα επίλυσης  που βασίζονται στη  διάδοση περιορισμών, μοντελοποιούν τον 

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

αφαιρώντας  τις  τιμές  που  δε  συμμετέχουν  σε  καμία  λύση  λόγω  ασυνέπειας.  Το  βασικό 

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

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

 

2.5.2 SAT 

Τα Προβλήματα Ικανοποίησης Boolean (B-SAT ή πιο γνωστά ως SAT από τον όρο 

Satisfiability) είναι προβλήματα απόφασης που διατυπώνονται στη θεωρία πολυπλοκότητας. 

Αποτελούν  πεδίο  που  αναλύει  την  επίλυση  Προβλημάτων  Ικανοποίησης  Περιορισμών  με