Αυτοαναφορικές, διαγώνιες μέθοδοι και πλήρης μελέτη του σχετικοποιημένου P^A=NP^A και P^B ≠ NP^B των Baker - Gill - Solovay - ΜΕΡΟΣ Α’ - Τσιαντού, Ευαγγελία (Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Εφαρμοσμένων Μαθηματικών και Φυσικών Επιστημών, 2014)
Η παρούσα εργασία αποτελεί μία προσέγγιση αυτοαναφορικών και διαγωνίων μεθόδων, ενώ παρουσιάζεται μία πλήρης μελέτη του σχετικοποιημένου προβλήματος P^A=NP^A και P^B≠NP^B των Baker, Gill και Solovay. Στο πρώτο μέρος, συζητούνται γνωστά αυτοαναφορικά παράδοξα σύμφωνα με το άρθρο [2] του Noson S. Yanofsky. Παρουσιάζεται μία προσπάθεια για έναν ενιαίο φορμαλισμό γνωστών παραδόξων, από τα θεωρήματα του Cantor, το παράδοξο του Russell και του ψεύτη, μέχρι και το πρόβλημα του τερματισμού του Turing. Στο δεύτερο μέρος προχωράμε σε μία αρκετά εκτενή μελέτη του «P έναντι NP», το οποίο αποτελεί το σημαντικότερο ανοιχτό πρόβλημα της υπολογιστικής πολυπλοκότητας και ένα από τα έξι σύγχρονα άλυτα μαθηματικά προβλήματα. Παρουσιάζεται η ιστορική αναδρομή και η φύση του προβλήματος, ορίζονται οι μηχανές Turing, οι εν λόγω κλάσεις πολυπλοκότητας, καθώς και η χωρική και χρονική πολυπλοκότητα. Ακολούθως, μελετάμε το θεώρημα του Savitch. Η εργασία ολοκληρώνεται, ενώ παρατίθενται αναλυτικά οι αποδείξεις P^A=NP^A και P^B≠NP^B των Baker, Gill και Solovay.