#p:πολυπλοκότητα Και Προσεγγιστικές Τεχνικές

Abstract

Η διπλωματική αυτή αφορά την κλάση #Ρ. Ασχολείται κυρίως με το ποιά προβλήματα περιέχει αυτή η κλάση ,πόσο δύσκολα είναι και τι μπορούμε να κάνουμε για να τα λύσουμε αποδοτικά έστω και με προσεγγιστικό τρόπο.Στο πρώτο κεφάλαιο ορίζουμε ποιά είναι η κλάση #P και συγκρίνουμε την πολυπλοκότητά της με αυτή της πολυωνυμικής ιεραρχίας(PH). Συμπεραίνουμε τελικά ότι το #Ρ δεν περιέχεται σε κανένα επίπεδο της PH και άρα μάλλον είναι πιο 'δύσκολο' από αυτή.Με δεδομένο λοιπόν ότι δεν είναι πολύ πιθανό να μπορέσουμε να λύσουμε ακριβώς με αποδοτικό τρόπο τα προβλήματα αυτής της κλάσης στρέφουμε την προσοχή μας στην έννοια της προσέγγισης. Στο δεύτερο κεφάλαιο αναφέρουμε όλους τους απαραίτητους ορισμούς - προσεγγιστικοί, πιθανοτικοί αλγόριθμοι - καθώς και την μέρχρι τώραεικόνα της κλάσης #P ως προς την ύπαρξη ή όχι FPRAS αλγορίθμων.Η ύπαρξη ή όχι FPRAS για κάποια προβλήματα είναι ακόμη ανοικτό ερώτημα και η απάντηση δεν μπορεί να δοθεί απλά. Για αυτό το λόγο στο τρίτο κεφάλαιο ασχολούμαστε με την συχέτιση του FPRAS με το FPAUS δηλαδή πολυωνυμικούς αλγορίθμους που επιτυχγάνουν σχεδόν ομοίομορφη δειγματοληψία χώρων αγνώστου διάστασης - αλλά πεπερασμένης. Αναγάγουμε με αυτό τον τρόπο την δημιουργία FPRAS στην ύπαρξη FPAUS για κάποιες κατηγορίες προβλημάτων. Στο τελευταίο κεφάλαιο αναφερόμαστε σύντομα σε μία άλλη κατηγοριοποίηση των προβλημάτων του \#P, που βασίζεται περισσότερο σε δομικά χαρακτηριστικά των προβλημάτων και επιδιώκουμε την συσχέτιση αυτώνμε τις κλάσεις που έχουν αναφερθεί στα προηγούμενα.Τα ερωτηματικά σε αυτή την ανάλυσηείναι πολλά και η σχέση κάθε άλλο παρά σαφής είναι αυτή τη στιγμή.Περεταίρω ανάλυση αυτού του θέματος καθώς και του ζητήματος της συσχέτισης FPRAS με FPAUS είναι δυνατή και σίγουρα ενδιαφέρουσα.