nondeterministic space is closed under complementation

Graduate Thesis uoadl:1324322 67 Read counter

Unit:
Τομέας Θεωρητικής Πληροφορικής
Library of the School of Science
Deposit date:
2015-09-01
Year:
2015
Author:
Μαζαράκης Ευγένιος
Supervisors info:
Σταύρος Κολλιόπουλος
Original Title:
Ο μη ντετερμινιστικός χώρος είναι κλειστός ως προς το συμπλήρωμα
Languages:
Greek
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
Index:
No
Number of index pages:
6
Contains images:
Yes
Number of references:
24
Number of pages:
37
document.pdf (568 KB) Open in new window