E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης - Πιθανοθεωρητικές μέθοδοι και εφαρμογές σε κάτω φράγματα πολυπλοκότητας

Αρχική Πιθανοθεωρητικές μέθοδοι και εφαρμογές σε κάτω φράγματα πολυπλοκότητας

Αποτελέσματα - Λεπτομέρειες

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000368496

Τίτλος

Πιθανοθεωρητικές μέθοδοι και εφαρμογές σε κάτω φράγματα πολυπλοκότητας

Άλλος τίτλος

Probabilistic Methods and Applications in Lower Complexity Bounds

Συγγραφέας

Χόνδρος, Αναστάσιος Θεόδωρος

Σύμβουλος διατριβής

Κολουντζάκης, Μιχάλης

Περίληψη

Σκοπός της εργασίας που ακολουθεί είναι να δείξει την «δύναμη» των πιθανοθεωρητικών μεθόδων, χάρη στις οποίες τελικά μπορούμε να αποφανθούμε εάν τελικά κάτι «υπάρχει» χωρίς αναγκαστικά να το κατασκευάσουμε. Έτσι, στα κεφάλαια 1 και 2, δείχνουμε την ύπαρξη υποσυνόλων του Ν τα οποία έχουν κάποιες συγκεκριμένες ιδιότητες. Συγκεκριμένα, στο κεφάλαιο 1, δείχνουμε την ύπαρξη ασυμπτωτικής προσθετικής βάσης με συνάρτηση αναπαράστασης μεγέθους O(log(x)), ενώ στο κεφάλαιο 2, την ύπαρξη και κατασκευή σε πολυωνυμικό χρόνο ενός sum-free συνόλου, από ένα δεδομένο υποσύνολο του Ν Στα κεφάλαια 3 και 4, ασχολούμαστε με την συνάρτηση parity και χρησιμοποιώντας πιθανοθεωρητικά επιχειρήματα πάλι, δείχνουμε ότι δεν μπορεί να υπολογιστεί από λογικά κυκλώματα σταθερού βάθους και πολυωνυμικού μεγέθους καθώς και κάποια άλλα φράγματα.

Φυσική περιγραφή

50 σ. : εικ. ; 28 εκ.

Γλώσσα

Αγγλικά

Θέμα

Probabilistic

Random Restrictions

Πιθανοθεωρητικός

Τυχαίος περιορισμός

Ημερομηνία έκδοσης

2011-07-15

Συλλογή