Στην παρούσα εργασία θα αναφερθούμε στο κατωφλικό φαινόμενο που εμφανίζεται στο k-SAT. Κύρια προσφορά της διπλωματικής είναι μια νέα απόδειξη του κάτω φράγματος στην περίπτωση του προβλήματος 2-SAT, όπου εκμεταλλευόμενοι γνωστά θεωρήματα από τη θεωρία τυχαίων γραφημάτων επιτυγχάνουμε μια ευκολότερη απόδειξη. Ξεκινάμε κάνοντας μια γενική παρουσίαση του προβλήματος της ικανοποιησιμότητας. Στο επόμενο κεφάλαιο παρουσιάζουμε κάποιους βασικούς ορισμούς και κάνουμε μια σύντομη αναδρομή στα αποτελέσματα που έχουν προκύψει. Αντικείμενο του τρίτου και τέταρτου κεφαλαίου είναι το 2-SAT όπου παρουσιάζονται αντιστοίχως η απόδειξη που δόθηκε από τον Goerdt[24] και μια νέα απόδειξη για το κάτω φράγμα με χρήση resolution. Στο τελευταίο κεφάλαιο στρέφουμε το ενδιαφέρον μας στην περίπτωση του 3-SAT και εξετάζουμε τις αποδείξεις ενός άνω και ενός κάτω κατωφλίου. / -