Unit:
Τομέας Θεωρητικής ΠληροφορικήςLibrary of the School of Science
Author:
Μαζαράκης Ευγένιος
Supervisors info:
Σταύρος Κολλιόπουλος
Original Title:
Ο μη ντετερμινιστικός χώρος είναι κλειστός ως προς το συμπλήρωμα
Translated title:
nondeterministic space is closed under complementation
Summary:
Στη πτυχιακή αυτή εργασία εξηγείται η μελέτη του Neil Immerman που δημοσιεύτηκε
το 1988 [23]. Για αυτή τη δημοσίευση του απονεμήθηκε το 1995 το βραβείο Godel
διότι απάντησε σε ένα ερώτημα που έμενε πάνω από τρεις δεκαετίες ανοικτό. Κύριος
στόχος της εργασίας αυτής είναι να εξηγήσουμε τι απέδειξε ο Neil Immerman αλλά
και
με ποιο τρόπο τα κατάφερε. Αρχικά αναφέρονται όλοι οι απαραίτητοι ορισμοί γύρω
από τις μηχανές Turing, την πολυπλοκότητα, τις κλάσεις πολυπλοκότητας, τις
διάφορες
σχέσεις που υπάρχουν ανάμεσά τους, τις γραμματικές. Αυτό είναι το απαραίτητο
υπόβαθρο που θα χρειαστούμε για να ακολουθήσουμε το συλλογισμό του Neil Immer-
man. Μετά παρουσιάζονται και εξηγούνται με απλό και κατανοητό τρόπο τα
περιεχόμενα
της δημοσίευσης του. Τέλος ακολουθούν τα συμπεράσματα που προκύπτουν από την
ενασχόλησή μας με τα αποτελέσματα στα οποία οδηγήθηκε ο Immerman.
Keywords:
Space Complexity, Turing Machine, Nondeterminism, Closed under Complementation, Complexity Classes
