Στην παρούσα εργασία θα αναφερθούμε στο κατωφλικό φαινόμενο που εμφανίζεται στο k-SAT. Κύρια προσφορά της διπλωματικής είναι μια νέα απόδειξη του κάτω φράγματος στην περίπτωση του προβλήματος 2-SAT, όπου εκμεταλλευόμενοι γνωστά θεωρήματα από τη θεωρία τυχαίων γραφημάτων επιτυγχάνουμε μια ευκολότερη απόδειξη.
Ξεκινάμε κάνοντας μια γενική παρουσίαση του προβλήματος της ικανοποιησιμότητας. Στο επόμενο κεφάλαιο παρουσιάζουμε κάποιους βασικούς ορισμούς και κάνουμε μια σύντομη αναδρομή στα αποτελέσματα που έχουν προκύψει. Αντικείμενο του τρίτου και τέταρτου κεφαλαίου είναι το 2-SAT όπου παρουσιάζονται αντιστοίχως η απόδειξη που δόθηκε από τον Goerdt[24] και μια νέα απόδειξη για το κάτω φράγμα με χρήση resolution. Στο τελευταίο κεφάλαιο στρέφουμε το ενδιαφέρον μας στην περίπτωση του 3-SAT και εξετάζουμε τις αποδείξεις ενός άνω και ενός κάτω κατωφλίου. / -
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/900 |
| Date | 29 August 2008 |
| Creators | Παρασκευάς, Αναστάσιος |
| Contributors | Καββαδίας, Δημήτριος, Καββαδίας, Δημήτριος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0026 seconds