Πιθανοτικός αλγόριθμος

Στην θεωρητική πληροφορική, ένας πιθανοτικός αλγόριθμος (ή τυχαιοποιημένος ή τυχαίος αλγόριθμος) είναι ένας αλγόριθμος που χρησιμοποιεί τυχαιότητα ως μέρος της λογικής του ή της διαδικασίας του. Ο αλγόριθμος παίρνει ομοιόμορφα τυχαία bits ως βοηθητική είσοδο τα οποία χρησιμοποιεί για να καθοδηγήσει την εκτέλεσή του, με στόχο να επιτύχει καλή απόδοση στη "μέση περίπτωση" (όπως αυτή ορίζεται σε σχέση με τα τυχαία bits). Επομένως είτε ο χρόνος εκτέλεσης είτε η έξοδος (ή και τα δύο) είναι τυχαίες μεταβλητές.

Οι πιθανοτικοί αλγόριθμοι διακρίνονται σε αυτούς που πάντοτε τερματίζουν με τη σωστή απάντηση, αλλά όπου ο αναμενόμενος χρόνος εκτέλεσης είναι πεπερασμένος (αλγόριθμοι Λας Βέγκας, για παράδειγμα ο αλγόριθμος ταξινόμησης Quicksort^[1]) και αλγόριθμους που με κάποια πιθανότητα μπορεί να δώσουν ένα λανθασμένο αποτέλεσμα (αλγόριθμοι Monte Carlo, για παράδειγμα ο αλγόριθμος Monte Carlo για το πρόβλημα του ελάχιστου συνόλου ανάδρασης κορυφών^[2]) ή να αποτύχουν να παράγουν αποτέλεσμα είτε σηματοδοτώντας μια αποτυχία είτε αποτυγχάνοντας να τερματίσουν. Σε ορισμένες περιπτώσεις, οι πιθανοτικοί αλγόριθμοι είναι το μόνο πρακτικό μέσο επίλυσης ενός προβλήματος.^[3]

Είναι κοινή πρακτική, οι πιθανοτικοί αλγόριθμοι προσεγγίζονται χρησιμοποιώντας μια γεννήτρια ψευδοτυχαίων αριθμών στη θέση μιας πραγματικής πηγής τυχαίων bits. Μια τέτοια υλοποίηση μπορεί να αποκλίνει από την αναμενόμενη θεωρητική συμπεριφορά και τις μαθηματικές εγγυήσεις που μπορεί να εξαρτώνται από την ύπαρξη μιας ιδανικής πραγματικής γεννήτριας τυχαίων αριθμών.

Παράδειγμα Επεξεργασία

Ως παράδειγμα, θα δούμε το πρόβλημα της εύρεσης ενός στοιχείου 'a' σε έναν πίνακα n στοιχείων.

Είσοδος : Ένας πίνακας $n\geq 2$ στοιχείων, στον οποίο τα μισά είναι a και τα άλλα μισά είναι b.

Έξοδος: Βρείτε ένα a στον πίνακα.

Δίνουμε δύο εκδοχές του αλγορίθμου, έναν αλγόριθμο Λας Βέγκας και έναν αλγόριθμο Μόντε Κάρλο .

Ξεκινάμε με τον αλγόριθμο Λας Βέγκας:

findingA_LV(array A, n)
begin
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
  until A[j] = 'a'
end

Αυτός ο αλγόριθμος πετυχαίνει με πιθανότητα 1. Ο αριθμός των επαναλήψεων δεν είναι σταθερός και μπορεί να είναι αυθαίρετα μεγάλος, αλλά η αναμενόμενη τιμή των επαναλήψεων είναι

\lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2

Επειδή είναι σταθερά, ο αναμενόμενος χρόνος εκτέλεσης για πολλές κλήσεις είναι $\Theta (1)$ .

Συνεχίζουμε με τον αλγόριθμο Μόντε Κάρλο:

findingA_MC(array A, n, k)
begin
  i := 0
  repeat
    // Τυχαία διαλέγουμε ένα από τα n στοιχεία.
    j = RandInt(1, n)
    i := i + 1
  until i = k or A[j] = 'a'
end

Αν βρεθεί ένα 'a', ο αλγόριθμος πετυχαίνει, διαφορετικά ο αλγόριθμος αποτυγχάνει. Αφού σε κάθε επανάληψη ο αλγόριθμος πετυχαίνει με πιθανότητα $1/2$ , και οι επαναλήψεις είναι ανεξάρτητες, μετά από k επαναλήψεις, η πιθανότητα να βρεθεί ένα ' a ' είναι:

$\Pr[{\text{βρέθηκε}}\ a]=1-(1/2)^{k}$

Δεν είναι εγγυημένο ότι ο αλγόριθμος θα πετύχει κάθε φορά, αλλά είναι εγγυημένο ότι ο χρόνος εκτέλεσης είναι πεπερασμένος, καθώς ο αριθμός των επαναλήψεων είναι πάντα μικρότερος ή ίσος του k. Θεωρώντας το k ως σταθερά, ο χρόνος εκτέλεσης (αναμενόμενος και απόλυτος) είναι $\Theta (1)$ .

Οι πιθανοτικοί αλγόριθμοι είναι ιδιαίτερα χρήσιμοι όταν υπάρχει ένας κακόβουλος "αντίπαλος" που προσπαθεί σκόπιμα να δώσει μία είσοδο στον αλγόριθμο ώστε να καθυστερήσει τον αλγόριθμο (βλ . χειρότερη περίπτωση πολυπλοκότητα και ανταγωνιστική ανάλυση (αλγόριθμοι)) όπως στο δίλημμα του φυλακισμένου. Αυτός είναι και ο λόγος που η τυχαιότητα είναι πανταχού παρούσα στην κρυπτογραφία. Σε κρυπτογραφικές εφαρμογές, δεν μπορούν να χρησιμοποιηθούν ψευδοτυχαίοι αριθμοί, αφού ο αντίπαλος μπορεί να τους προβλέψει, καθιστώντας τον αλγόριθμο ντετερμινιστικό. Επομένως, απαιτείται είτε μια πηγή "πραγματικά" τυχαίων αριθμών είτε μια κρυπτογραφικά ασφαλής γεννήτρια ψευδοτυχαίων αριθμών . Ένας άλλος τομέας στον οποίο η τυχαιότητα είναι εγγενής είναι ο κβαντικός υπολογισμός .

Στο παραπάνω παράδειγμα, ο αλγόριθμος Λας Βέγκας δίνει πάντα τη σωστή απάντηση, αλλά ο χρόνος εκτέλεσης του είναι μια τυχαία μεταβλητή. Ο αλγόριθμος Monte Carlo (που σχετίζεται με τη μέθοδο προσομοίωσης Monte Carlo) εγγυάται ότι θα τερματίσει σε ένα πεπερασμένο χρονικό διάστημα, το μήκος του οποίου φράζεται από μία συνάρτηση του μεγέθους της εισόδου και της παραμέτρου k, αλλά επιτρέπει μια μικρή πιθανότητα σφάλματος. Παρατηρήστε ότι οποιοσδήποτε αλγόριθμος Λας Βέγκας μπορεί να μετατραπεί σε αλγόριθμο Μόντε Κάρλο (μέσω της ανισότητας Μάρκοφ), βάζοντάς του να επιστρέψει μία αυθαίρετη (πιθανώς λανθασμένη απάντηση) εάν αποτύχει να ολοκληρωθεί εντός του καθορισμένου χρόνου. Αντίθετα, εάν έχουμε έναν αποδοτικό αλγόριθμο για να ελέγξουμε εάν μια απάντηση είναι σωστή (στο παραπάνω παράδειγμα αυτό ήταν απλά `A[j] = a'), τότε ένας αλγόριθμος Monte Carlo μπορεί να μετατραπεί σε αλγόριθμο Λας Βέγκας εκτελώντας τον αλγόριθμο Monte Carlo επανειλημμένα μέχρι να λάβουμε μια σωστή απάντηση.

Υπολογιστική πολυπλοκότητα Επεξεργασία

Η θεωρία της υπολογιστικής πολυπλοκότητας μοντελοποιεί πιθανοτικούς αλγόριθμους με τις πιθανοτικές μηχανές Turing. Στον τομέα έχουν μελετηθεί και οι αλγόριθμοι Λας Βέγκας και Μόντε Κάρλο, και επίσης έχουν διατυπωθεί αρκετές άλλες κλάσεις πολυπλοκότητας σχετικές με την τυχαιότητα. Η πιο βασική πιθανοτική κλάση πολυπλοκότητας είναι η RP, η οποία περιλαμβάνει προβλήματα απόφασης για τα οποία υπάρχει ένας αποδοτικός (που τρέχει σε πολυωνυμικό χρόνο) πιθανοτικός αλγόριθμος (ή ισοδύναμα μία πιθανοτική μηχανή Turing) που αναγνωρίζει τις περιπτώσεις ΟΧΙ με απόλυτη βεβαιότητα και αναγνωρίζει τις περιπτώσεις ΝΑΙ με πιθανότητα τουλάχιστον 1/2. Το συμπλήρωμα της κλάσης RP είναι η κλάση co-RP. Τα προβλήματα που έχουν (πιθανώς μη τερματιζόμενους) αλγόριθμους με πολυωνυμικό αναμενόμενο χρόνο εκτέλεσης και των οποίων η έξοδος είναι πάντα σωστή ανήκουν στην κλάση ZPP .

Η κλάση των προβλημάτων για τα οποία οι αλγόριθμοι έχουν πιθανότητα σφάλματος και στις ΝΑΙ και στις ΟΧΙ περιπτώσεις ονομάζεται BPP. Αυτή η κλάση είναι η αντίστοιχη πιθανοτική κλάση του P, δηλ το BPP αντιπροσωπεύει την κατηγορία των αποδοτικών πιθανοτικών αλγορίθμων.

Ιστορία Επεξεργασία

Ταξινόμηση Επεξεργασία

Ο αλγόριθμος Quicksort για την ταξινόμηση ανακαλύφθηκε από τον Τόνι Χορ το 1959, και στη συνέχεια δημοσιεύτηκε το 1961.^[4] Την ίδια χρονιά, ο Χορ δημοσίευσε τον αλγόριθμο Quickselect^[5] που βρίσκει το διάμεσο στοιχείο μιας λίστας σε γραμμικό αναμενόμενο χρόνο. Το πρόβλημα του αν υπήρχε ντετερμινιστικός αλγόριθμος γραμμικού χρόνου παρέμεινε ανοιχτό μέχρι το 1973.^[6]

Θεωρία αριθμών Επεξεργασία

Το 1917, ο Henry Cabourn Pocklington εισήγαγε έναν πιθανοτικό αλγόριθμο γνωστό ως αλγόριθμος Pocklington για την αποτελεσματική εύρεση τετραγωνικών ριζών modulo πρώτων αριθμών.^[7] Το 1970, οElwyn Berlekamp εισήγαγε έναν τυχαιοποιημένο αλγόριθμο για τον αποτελεσματικό υπολογισμό των ριζών ενός πολυωνύμου σε ένα πεπερασμένο πεδίο.^[8] Το 1977, ο Robert M. Solovay και ο Volker Strassen ανακάλυψαν έναν αλγόριθμο για να ελέγχει αν ένας αριθμός είναι πρώτος σε πολυωνυμικό χρόνο. Λίγο αργότερα, ο Michael O. Rabin έδειξε ότι ο αλγόριθμος ελέγχου πρώτων του Miller (του 1976) μπορεί επίσης να μετατραπεί σε έναν πολυωνυμικό πιθανοτικό αλγόριθμο. Εκείνη την εποχή, δεν ήταν γνωστός κάποιος ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου για τον έλεγχο πρώτων αριθμών.

Δομές δεδομένων Επεξεργασία

Μία από τις πρώτες πιθανοτικές δομές δεδομένων είναι ο πίνακας κατακερματισμού, ο οποίος εισήχθη το 1953 από τον Hans Peter Luhn στην IBM.^[9] Ο πίνακας κατακερματισμού του Luhn χρησιμοποιούσε μία αλυσίδα για την επίλυση συγκρούσεων και ήταν επίσης μια από τις πρώτες εφαρμογές συνδεδεμένων λιστών.^[9] Στη συνέχεια, το 1954, οι Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester και Arthur Samuel της IBM Research εισήγαγαν τη γραμμική εξέταση^[9], αν και ο Andrey Ershov ανεξάρτητα είχε την ίδια ιδέα το 1957.^[9] Το 1962, ο Donald Knuth πραγματοποίησε την πρώτη σωστή ανάλυση γραμμικής εξέτασης,^[9] αν και το σημείωμα που είχε την ανάλυσή του δεν δημοσιεύτηκε μέχρι αργότερα.^[10] Η πρώτη δημοσιευμένη ανάλυση ήταν από τον Konheim και τον Weiss το 1966.^[11]

Οι πρώτες αναλύσεις των πινάκων κατακερματισμού υπέθεταν ότι είτε υπάρχει πρόσβαση σε μια πλήρως τυχαία συνάρτηση κατακερματισμού είτε ότι τα κλειδιά ήταν τυχαία.^[9] Το 1979, οι Carter και Wegman εισήγαγαν τις καθολικές συναρτήσεις κατακερματισμού^[12] και έδειξαν ότι μπορούν να χρησιμοποιηθούν για την υλοποίηση αλυσιδωτών πινάκων κατακερματισμού με σταθερό αναμενόμενο χρόνο ανά πράξη.

Το 1970, ο Burton Howard Bloom εισήγαγε τα φίλτρα Bloom, μία δομή δεδομένων που δίνει προσεγγιστικές απαντήσεις για το αν ένα στοιχείο x ανήκει σε ένα σύνολο S. ^[13] Το 1989, ο Raimund Seidel και η Cecilia R. Aragon εισήγαγαν ένα πιθανοτικό και ισορροπημένο δυαδικό δέντρο αναζήτησης γνωστό ως treap.^[14] Την ίδια χρονιά, ο William Pugh παρουσίασε ένα άλλο τυχαιοποιημένο δέντρο αναζήτησης γνωστό ως λίστα παράλειψης.^[15]

Χρήσεις στη Συνδυαστική Επεξεργασία

Πριν γίνουν διαδεδομένοι οι πιθανοτικοί αλγόριθμοι στην επιστήμη των υπολογιστών, ο Πολ Έρντος έκανε δημοφιλή τη χρήση πιθανοτικών μεθόδων ως μια μαθηματική τεχνική για την απόδειξη ύπαρξης μαθηματικών αντικειμένων. Αυτή η τεχνική έχει γίνει γνωστή ως πιθανοτική μέθοδος.^[16] Ο Erdős έκανε την πρώτη του εφαρμογή της πιθανοτικής μεθόδου το 1947, όταν χρησιμοποίησε μια απλή πιθανοτική κατασκευή για να αποδείξει την ύπαρξη γράφων Ramsey. ^[17] Επίσης χρησιμοποίησε έναν πολύ πιο περίπλοκο πιθανοτικό αλγόριθμο το 1959 για να διαπιστώσει την ύπαρξη γράφων με υψηλή περιφέρεια και χρωματικό αριθμό.^[18]^[16]

Παραδείγματα Επεξεργασία

Quicksort Επεξεργασία

Η γρήγορη ταξινόμηση είναι ένας γνωστός, ευρέως χρησιμοποιούμενος αλγόριθμος ο οποίος κάνει χρήση της τυχαιότητας. Πολλές ντετερμινιστικές εκδοχές αυτού του αλγορίθμου (π.χ. που διαλέγουμε πάντα το πρώτο στοιχείο ως άξονα) χρειάζονται Θ(n²) χρόνο για να ταξινομήσουν n αριθμούς για μία κατηγορία καλά διατυπωμένων εισόδων (π.χ. τους ήδη ταξινομημένους πίνακες). Ωστόσο, εάν ο αλγόριθμος επιλέγει τον άξονα ομοιόμορφα στην τύχη (από τα υπολειπόμενα στοιχεία), τότε με μεγάλη πιθανότητα τελειώνει σε O(n log n) χρόνο ανεξάρτητα από τα χαρακτηριστικά της εισόδου.

Πιθανοτικές σταδιακές κατασκευές στη γεωμετρία Επεξεργασία

Στην υπολογιστική γεωμετρία, μια κλασσική τεχνική για την κατασκευή μιας γεωμετρικής δομής όπως το κυρτό περίβλημα ή η τριγωνοποίηση Delaunay είναι πρώτα να πάρουμε μία τυχαία μετάθεση των σημείων εισόδου και στη συνέχεια να τα εισάγουμε στην υπάρχουσα δομή το ένα μετά το άλλο. Η τυχαιότητα της σειράς που τα εισάγουμε διασφαλίζει ότι ο αναμενόμενος συνολικός αριθμός αλλαγών στη δομή είναι μικρός και έτσι ο αναμενόμενος χρόνος εκτέλεσης του αλγορίθμου είναι μικρός. Αυτή η τεχνική είναι γνωστή ως τυχαιοποιημένη σταδιακή κατασκευή.^[19]

Ελάχιστη τομή Επεξεργασία

Είσοδος: Ένας γράφος G(V, E).

Έξοδος: Μία τομή που χωρίζει τις κορυφές στα σύνολα L και R, και έχει τον ελάχιστο αριθμό ακμών μεταξύ των L και R.

Η συστολή δύο κορυφών u και v σε έναν (πολυ-)γράφο δίνει μία νέα κορυφή u' με ακμές που είναι η ένωση των ακμών που προσπίπτουν είτε στον u είτε στον v, εξαιρουμένων των ακμών μεταξύ των u και v. Το Σχήμα 1 δίνει ένα παράδειγμα συστολής των Α και Β. Μετά τη συστολή, ο γράφος που προκύπτει μπορεί να έχει παράλληλες ακμές, αλλά δεν περιέχει βρόχους.

Σχήμα 2: Επιτυχής εκτέλεση του αλγορίθμου του Karger σε έναν γράφο 10 κορυφών. Η ελάχιστη τομή έχει μέγεθος 3 και υποδεικνύεται από τα χρώματα κορυφής.

Σχήμα 1: Συστολή των κορυφών Α και Β.

Ο απλός αλγόριθμος του Karger^[20]:

begin 
   i := 1 
   repeat 
      repeat 
         Διαλέγουμε μία τυχαία ακμή (u,v) ∈ E στον G
         Διαγράφουμε τις κορυφές u και v
         Προσθέτουμε τη συστολή τους u΄
      until να μείνουν ακριβώς δύο κουρφές
      Λαμβάνουμε την αντίστοιχη τομή Cᵢ
      i := i + 1
   until i = m 
   Τυπώνουμε την ελάχιστη τομή από τις C₁, C₂, ..., Cₘ.
end

Ο αλγόριθμος επαναλαμβάνει τον εσωτερικό βρόχο $m$ φορές, που βρίσκει μία τομή $C_{i}$ . Ο χρόνος εκτέλεσης του εσωτερικού βρόχου είναι $O(n)$ , όπου n το πλήθος των κορυφών του γράφου. Μετά από m εκτελέσεις του εξωτερικού βρόχου, κρατάμε την ελάχιστη τομή μεταξύ όλων των αποτελεσμάτων. Το Σχήμα 2 δίνει ένα παράδειγμα μιας εκτέλεσης του αλγορίθμου, στο τέλος της οποίας λαμβάνουμε μια τομή ή μεγέθους 3.

Λήμμα 1 — Έστω k το μέγεθος της ελάχιστης τομής, και έστω $C = {e 1, e 2, ..., e k}$ η ελάχιστη τομή. Αν, κατά την i-οστή επανάληψη, δεν υπάρχει ακμή $e \in C$ που επιλέγεται για συστολή, τότε $C i = C$ .

Απόδειξη

Αν ο G δεν είναι συνδεδεμένος, τότε οι κορυφές του G μπορούν να χωριστούν στα σύνολα L και R χωρίς καμία ακμή μεταξύ τους. Επομένως, η ελάχιστη τομή ενός μη-συνδεδεμένου γράφου είναι 0. Τώρα, έστω ότι ο G είναι συνδεδεμένος. Έστω $V = L \cup R$ ο διαμερισμός του V που ορίζεται από $C : C = { {u, v} \in E : u \in L, v \in R$ } (που είναι καλώς-ορισμένο αφού ο G είναι συνδεδεμένος). Θεωρούμε μία ακμή {u,v} του C. Αρχικά, u,v είναι δύο διαφορετικές κορυφές. Όσο διαλέγουμε μία ακμή $f\neq e$ , οι $u$ και $v$ δεν ενώνονται. Επομένως, στο τέλος του αλγορίθμου, έχουμε δύο σύνθετες κορυφές που καλύπτουν ολόκληρο τον γράφο, ένας εκ των οποίων έχει τις κορυφές $L$ και ο άλλος τις κορυφές $R$ . Όπως στο Σχήμα 2, το μέγεθος της ελάχιστης τομής είναι 1, και $C=\{(A,B)\}$ . Αν δεν διαλέξουμε τα $(A,B)$ για συστολή, τότε θα πάρουμε την ελάχιστη τομή.

Λήμμα 2 — Έστω ένας πολυγράφος $G$ με $p$ κορυφές και ο οποίος έχει μέγεθος ελάχιστης τομής $k$ , τότε ο $G$ έχει τουλάχιστον $pk/2$ ακμές.

Απόδειξη

Επειδή η ελάχιστη τομή έχει μέγεθος $k$ , κάθε κορυφή $v$ πρέπει να ικανοποιεί $\operatorname {deg} (v)\geq k$ . Επομένως, το άθροισμα των βαθμών είναι τουλάχιστον $pk$ . Αλλά είναι γνωστό ότι το άθροισμα των βαθμών των κορυφών είναι ίσο με $2|E|$ . Συνδυάζοντας αυτά, καταλήγουμε στο συμπέρασμα.

Ανάλυση του αλγορίθμου Επεξεργασία

Η πιθανότητα να πετύχει ο αλγόριθμος είναι 1 μείον την πιθανότητα να αποτύχουν όλες οι προσπάθειες. Επειδή κάθε επανάληψη είναι ανεξάρτητη, η πιθανότητα να αποτύχουν όλες οι προσπάθειες είναι

\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).

Από το Λήμμα 1, η πιθανότητα να έχουμε

C i = C

είναι η πιθανότητα να μην επιλέξαμε καμία ακμή του C κατά την επανάληψη i . Θεωρήστε τον εσωτερικό βρόχο και έστω

G j

ο γράφος μετά από j συστολές ακμών για

j \in {0, 1, \dots, n - 3}

. Τότε ο

G j

έχει

n - j

κορυφές. Χρησιμοποιούμε τον κανόνα της αλυσίδας για την κατά συνθήκη πιθανότητα. Η πιθανότητα η ακμή που επιλέχθηκε στην επανάληψη j να μην είναι στο C, δεδομένου ότι δεν έχουμε επιλέξει καμία ακμή του C προηγουμένως, είναι

1-{\tfrac {k}{|E(G_{j})|}}

. Παρατηρήστε ότι ο

G j

εξακολουθεί να έχει ελάχιστη τομή μεγέθους k, επομένως από το Λήμμα 2, εξακολουθεί να έχει τουλάχιστον

{\tfrac {(n-j)k}{2}}

ακμές.

Επομένως, $1-{\tfrac {k}{|E(G_{j})|}}\geq 1-{\tfrac {2}{n-j}}={\tfrac {n-j-2}{n-j}}$ .

Συνεπώς, χρησιμοποιώντας τον κανόνα της αλυσίδας, η πιθανότητα να βρεθεί η ελάχιστη τομή C είναι

\Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).

Μετά την απλοποίηση λαμβάνουμε ότι

\Pr[C_{i}=C]\geq {\tfrac {2}{n(n-1)}}

. Έτσι η πιθανότητα να πετύχει ο αλγόριθμος είναι τουλάχιστον

1-\left(1-{\tfrac {2}{n(n-1)}}\right)^{m}

. Θέτοντας

m={\tfrac {n(n-1)}{2}}\ln n

, η πιθανότητα είναι τουλάχιστον

1-{\tfrac {1}{n}}

. Καταλήγουμε ότι ο αλγόριθμος βρίσκει την ελάχιστη τομή με πιθανότητα τουλάχιστον

1-{\tfrac {1}{n}}

, σε χρόνο

O(mn)=O(n^{3}\log n)

.

Αποτυχαιοποίηση Επεξεργασία

Η τυχαιότητα μπορεί να θεωρηθεί ως ένας πόρος, όπως είναι ο χώρος και ο χρόνος. Η αποτυχαιοποίηση είναι η διαδικασία αφαίρεσης της τυχαιότητας (ή χρήσης όσο το δυνατόν λιγότερης από αυτήν) από έναν πιθανοτικό αλγόριθμο. Δεν είναι προς το παρόν γνωστό εάν όλοι οι αλγόριθμοι μπορούν να αποτυχαιοποιηθούν χωρίς να αυξηθεί σημαντικά ο χρόνος εκτέλεσης τους. Για παράδειγμα, στην θεωρία πολυπλοκότητας, είναι άγνωστο εάν P = BPP, δηλαδή, δεν γνωρίζουμε εάν μπορούμε να πάρουμε έναν αυθαίρετο τυχαιοποιημένο αλγόριθμο που εκτελείται σε πολυωνυμικό χρόνο με μικρή πιθανότητα σφάλματος και να τον αποτυχαιοποιήσουμε ώστε να εκτελείται σε πολυωνυμικό χρόνο χωρίς τη χρήση τυχαιότητας.

Υπάρχουν κάποιες γενικές μέθοδοι που μπορούν να χρησιμοποιηθούν για την αποτυχαιοποίηση συγκεκριμένων τυχαιοποιημένων αλγορίθμων:

η μέθοδος της κατά συνθήκη πιθανότητας και η γενίκευσή της, με τους απαισιόδοξους εκτιμητές
η θεωρία ασυμφωνίας (η οποία χρησιμοποιείται κυρίως για την αποτυχαιοποίηση γεωμετρικών αλγορίθμων)
η εκμετάλλευση περιορισμένης ανεξαρτησίας μεταξύ των τυχαίων μεταβλητών που χρησιμοποιούνται από τον αλγόριθμο, όπως η ανεξαρτησία ανά δύο που χρησιμοποιείται στον καθολικό κατακερματισμό
η χρήση γράφων επεκτατών για την ενίσχυση μιας μικρής ποσότητας αρχικής τυχαιότητας (αυτή η τελευταία προσέγγιση αναφέρεται επίσης ως δημιουργία ψευδοτυχαίων bits από μια τυχαία πηγή και οδηγεί στο σχετικό θέμα της ψευδοτυχαιότητας)
αλλαγή του τυχαιοποιημένου αλγόριθμου για χρήση μιας συνάρτησης κατακερματισμού ως πηγή τυχαιότητας για τις εργασίες του αλγορίθμου και, στη συνέχεια, αποτυχαιοποίηση του αλγορίθμου με ωμή βία όλων των πιθανών παραμέτρων (seeds) της συνάρτησης κατακερματισμού. Αυτή η τεχνική χρησιμοποιείται συνήθως για την εξαντλητική αναζήτηση ενός δειγματοληπτικού χώρου και κάνει τον αλγόριθμο ντετερμινιστικό (π.χ. πιθανοτικοί αλγόριθμοι γράφων)

Εκεί που η τυχαιότητα βοηθάει Επεξεργασία

Για τις μηχανές Turing, είναι ανοιχτό πρόβλημα εάν η δυνατότητα να κάνουμε τυχαίες επιλογές επιτρέπει την επίλυση ορισμένων προβλημάτων σε πολυωνυμικό χρόνο που δεν μπορούν να λυθούν σε πολυωνυμικό χρόνο χωρίς αυτήν τη δυνατότητα. Το πρόβλημα συνοψίζεται στο αν P = BPP. Ωστόσο, σε άλλα πλαίσια, υπάρχουν συγκεκριμένα παραδείγματα προβλημάτων όπου η τυχαιοποίηση προσφέρει αυστηρά καλύτερα αποτελέσματα.

Με βάση το αρχικό παράδειγμα: δοσμένης μιας εκθετικά μεγάλης συμβολοσειράς 2^k χαρακτήρων, όπου οι μισοί χαρακτήρες είναι a και οι άλλοι μισοί είναι b, μια μηχανή τυχαίας πρόσβασης χρειάζεται 2^k−1 προσβάσεις στον πίνακα στη χειρότερη περίπτωση για να βρει την θέση ενός a. Εάν επιπλέον έχει τη δυνατότητα να κάνει τυχαίες επιλογές, τότε μπορεί να λύσει αυτό το πρόβλημα σε έναν αναμενόμενο πολυωνυμικό αριθμό προσβάσεων.
Στην πολυπλοκότητα της επικοινωνίας, η ισότητα δύο συμβολοσειρών μπορεί να επαληθευτεί σε κάποια αξιοπιστία χρησιμοποιώντας $\log n$ bits επικοινωνίας με ένα πρωτόκολλο που κάνει χρήση τυχαιότητας. Από την άλλη οποιοδήποτε ντετερμινιστικό πρωτόκολλο απαιτεί $\Theta (n)$ bits αν υπάρχει ένας δυνατός αντίπαλος.^[21]
Ο όγκος ενός κυρτού σώματος μπορεί να εκτιμηθεί με έναν τυχαιοποιημένο αλγόριθμο με αυθαίρετη ακρίβεια σε πολυωνυμικό χρόνο.^[22] Οι Bárány και Füredi έδειξαν ότι κανένας ντετερμινιστικός αλγόριθμος δεν μπορεί να κάνει το ίδιο. ^[23] Αυτό ισχύει άνευ όρων, δηλαδή χωρίς να βασιζόμαστε σε οποιεσδήποτε θεωρητικές υποθέσεις πολυπλοκότητας, υποθέτοντας ότι το κυρτό σώμα μπορεί να διερευνηθεί μόνο ως μαύρο κουτί.
Στην θεωρία πολυπλοκότητας, η κλάση IP αποτελείται από όλες τις γλώσσες που μπορούν να γίνουν αποδεκτές (με μεγάλη πιθανότητα) από μια αλληλεπίδραση πολυωνυμικού μήκους μεταξύ ενός πανίσχυρου αποδείκτη και ενός επαληθευτή που εφαρμόζει έναν αλγόριθμο BPP. Ισχύει ότι IP = PSPACE.^[24] Ωστόσο, εάν απαιτείται ο επαληθευτής να είναι ντετερμινιστικός, τότε ισχύει ότι IP = NP .
Σε ένα δίκτυο χημικών αντιδράσεων (ένα πεπερασμένο σύνολο αντιδράσεων όπως A+B → 2C + D που λειτουργούν σε έναν πεπερασμένο αριθμό μορίων), η ικανότητα να φθάσουμε ποτέ σε μια κατάσταση από μια αρχική κατάσταση είναι αποφασίσιμη, ενώ προσεγγίζεται ακόμη και η πιθανότητα. Η επίτευξη μιας δεδομένης κατάστασης στόχου (χρησιμοποιώντας την τυπική πιθανότητα που βασίζεται στη συγκέντρωση για την οποία θα συμβεί η επόμενη αντίδραση) δεν μπορεί να αποφασιστεί. Πιο συγκεκριμένα, μια περιορισμένη μηχανή Turing μπορεί να προσομοιωθεί ώστε με μεγάλη πιθανότητα να λειτουργεί σωστά πάντοτε, μόνο εάν χρησιμοποιηθεί ένα τυχαίο δίκτυο χημικής αντίδρασης. Με ένα απλό μη ντετερμινιστικό δίκτυο χημικών αντιδράσεων (οποιαδήποτε πιθανή αντίδραση μπορεί να συμβεί στη συνέχεια), η υπολογιστική ισχύς περιορίζεται σε πρωταρχικές αναδρομικές συναρτήσεις . ^[25]

Περαιτέρω ανάγνωση Επεξεργασία

Ελληνικά βιβλία Επεξεργασία

Σωτήρης Ε. Νικολετσέας· Παύλο Γ. Σπυράκης (2003). Στοιχεία της πιθανοτικής μεθόδου: Μαθηματικές θεμελειώσεις της επιστήμης των υπολογιστών (PDF). Αθήνα: Gutenberg.
Τσίχλας, Κωνσταντίνος· Γούναρης, Αναστάσιος· Μανωλόπουλος, Ιωάννης (2015). «Κεφάλαιο 13: Τυχαίοι Αλγόριθμοι». Σχεδίαση και ανάλυση αλγορίθμων. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις.
Παγουρτζής, Αριστείδης· Ζάχος, Ευστάθιος (2015). «Κεφάλαιο 4: Αλγόριθμοι στην Κρυπτογραφία». Υπολογιστική κρυπτογραφία. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-960-603-276-9.
Δραζιώτης, Κ. (2022). «Κεφάλαιο 9: Τεστ Πιστοποίησης πρώτων αριθμών». Εισαγωγή στην Κρυπτογραφία. Αθήνα: Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. ISBN 978-618-85820-5-7.

Ξενόγλωσσα βιβλία Επεξεργασία

Mitzenmacher, Michael· Upfal, Eli (2017). Probability and computing: randomization and probabilistic techniques in algorithms and data analysis (2nd έκδοση). Cambridge: Cambridge university press. ISBN 978-1107154889.
Motwani, Rajeev· Raghavan, Prabhakar. Randomized algorithms (9th printing έκδοση). Cambridge New York Melbourne: Cambridge University Press. ISBN 978-0521474658.
Alon, Noga· Spencer, Joel H. (2015). The probabilistic method (4η έκδοση). Hoboken, New Jersey: Wiley. ISBN 978-1-119-06195-3.
Dubhashi, Devdatt· Panconesi, Alessandro (2012). Concentration of measure for the analysis of randomized algorithms. Cambridge New York Melbourne: Cambridge University Press. ISBN 978-1107606609.
Mulmuley, Ketan (1993). Computational geometry: an introduction through randomized algorithms (Transferred to digital print on demand έκδοση). Upper Saddle River, NJ: Prentice Hall. ISBN 978-0133363630.
Cormen, Thomas H.· =Leiserson, Charles Eric· Rivest, Ronald Linn· Stein, Clifford. «Probabilistic analysis and randomized algorithms». Introduction to algorithms (3η έκδοση). Cambridge, Massachusetts London, England: MIT Press. ISBN 978-0262033848.
Kleinberg, Jon· Tardos, Éva (2014). «Chapter 12: Randomized algorithms». Algorithm design (1η έκδοση). Harlow: Pearson. ISBN 978-1-292-02394-6.

Επισκοπήσεις Επεξεργασία

Karger, David R. (1994). Random sampling in cut, flow, and network design problems, σελ. 648–657. doi:10.1145/195058.195422.
Kannan, Ravindran; Vempala, Santosh (1 Μαΐου 2017). «Randomized algorithms in numerical linear algebra». Acta Numerica 26: 95–135. doi:10.1017/S0962492917000058.
Bentley, Jon Louis; Lueker, George S. (1982). «Probabilistic Analysis of Algorithms». Applied Probability-Computer Science: The Interface Volume 1: 137–162. doi:10.1007/978-1-4612-5791-2_5.

Δείτε επίσης Επεξεργασία

Παραπομπές Επεξεργασία

↑ Hoare, C. A. R. (July 1961). «Algorithm 64: Quicksort». Commun. ACM 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.
↑ Kudelić, Robert (2016-04-01). «Monte-Carlo randomized algorithm for minimal feedback arc set problem». Applied Soft Computing 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
↑ "Για τον έλγεχο πρώτων αριθμών πολύ μεγάλων αριθμών που έχουν επιλεγεί τυχαία, η πιθανότητα να πετύχουμε μία τιμή που ξεγελάει τον έλεγχο του Φερμά είναι μικρότερη από την πιθανότητα η κοσμική ακτινοβολία να κάνει έναν υπολογιστή να κάνει λάθος καθώς τρέχει έναν 'σωστό' αλγόριθμο. Το αν θα θεωρήσουμε έναν αλγόριθμο να μην είναι ικανοποιητικός για τον πρώτο λόγο και όχι για τον δεύτερο είναι η διαφορά μεταξύ των μαθηματικών και της μηχανικής." Hal Abelson και Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2 Αρχειοθετήθηκε 2006-09-03 στο Wayback Machine..
↑ Hoare, C. A. R. (July 1961). «Algorithm 64: Quicksort» (στα αγγλικά). Communications of the ACM 4 (7): 321. doi:10.1145/366622.366644. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/366622.366644.
↑ Hoare, C. A. R. (July 1961). «Algorithm 65: find» (στα αγγλικά). Communications of the ACM 4 (7): 321–322. doi:10.1145/366622.366647. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/366622.366647.
↑ Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973). «Time bounds for selection» (στα αγγλικά). Journal of Computer and System Sciences 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9. https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339.
↑ Williams, H. C.; Shallit, J. O. (1994), «Factoring integers before computers», στο: Gautschi, Walter, επιμ., Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, 48, Amer. Math. Soc., Providence, RI, σελ. 481–531, doi:10.1090/psapm/048/1314885 ; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".
↑ Berlekamp, E. R. (1971). «Factoring polynomials over large finite fields». Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 (στα Αγγλικά). Los Angeles, California, United States: ACM Press. σελ. 223. ISBN 9781450377867.
↑ ^9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 Knuth, Donald E. (1998). The art of computer programming, volume 3: sorting and searching (2η έκδοση). USA: Addison Wesley Longman Publishing Co., Inc. σελίδες 536–549. ISBN 978-0-201-89685-5.
↑ Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03
↑ Konheim, Alan G.; Weiss, Benjamin (November 1966). «An Occupancy Discipline and Applications». SIAM Journal on Applied Mathematics 14 (6): 1266–1274. doi:10.1137/0114101. ISSN 0036-1399. http://dx.doi.org/10.1137/0114101.
↑ Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). «Universal classes of hash functions» (στα αγγλικά). Journal of Computer and System Sciences 18 (2): 143–154. doi:10.1016/0022-0000(79)90044-8. ISSN 0022-0000.
↑ Bloom, Burton H. (July 1970). «Space/time trade-offs in hash coding with allowable errors». Communications of the ACM 13 (7): 422–426. doi:10.1145/362686.362692. ISSN 0001-0782. http://dx.doi.org/10.1145/362686.362692.
↑ Aragon, C.R.· Seidel, R.G. (Οκτωβρίου 1989). «Randomized search trees». 30th Annual Symposium on Foundations of Computer Science. σελίδες 540–545. ISBN 0-8186-1982-1.
↑ Pugh, William (1989). Concurrent Maintenance of Skip Lists (Τεχνική αναφορά). Dept. of Computer Science, U. Maryland. CS-TR-2222.
↑ ^16,0 ^16,1 Alon, Noga (2016). The probabilistic method. Joel H. Spencer (Fourth έκδοση). Hoboken, New Jersey. ISBN 978-1-119-06195-3.
↑ P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR8,479d; Zentralblatt 32,192.
↑ Erdös, P. (1959). «Graph Theory and Probability» (στα αγγλικά). Canadian Journal of Mathematics 11: 34–38. doi:10.4153/CJM-1959-003-9. ISSN 0008-414X. https://archive.org/details/sim_canadian-journal-of-mathematics_1959_11_1/page/34.
↑ Seidel R. Backwards Analysis of Randomized Geometric Algorithms.
↑ A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.
↑ Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834 . For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.
↑ Dyer, M.; Frieze, A.; Kannan, R. (1991), «A random polynomial-time algorithm for approximating the volume of convex bodies», Journal of the ACM 38 (1): 1–17, doi:10.1145/102782.102783, http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf
↑ Füredi, Z.; Bárány, I. (1986), «Computing the volume is difficult», Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986), New York, NY: ACM, σελ. 442–447, doi:10.1145/12130.12176, ISBN 0-89791-193-8, https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf
↑ Shamir, A. (1992), «IP = PSPACE», Journal of the ACM 39 (4): 869–877, doi:10.1145/146585.146609
↑ Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), «Programmability of chemical reaction networks», στο: Condon, Anne; Harel, David; Kok, Joost N. και άλλοι, επιμ., Algorithmic Bioprocesses, Natural Computing Series, Springer-Verlag, σελ. 543–584, doi:10.1007/978-3-540-88869-7_27, https://authors.library.caltech.edu/26121/1/etr090.pdf .

[1] Hoare, C. A. R. (July 1961). «Algorithm 64: Quicksort». Commun. ACM 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.

[2] Kudelić, Robert (2016-04-01). «Monte-Carlo randomized algorithm for minimal feedback arc set problem». Applied Soft Computing 41: 235–246. doi:10.1016/j.asoc.2015.12.018.

[3] "Για τον έλγεχο πρώτων αριθμών πολύ μεγάλων αριθμών που έχουν επιλεγεί τυχαία, η πιθανότητα να πετύχουμε μία τιμή που ξεγελάει τον έλεγχο του Φερμά είναι μικρότερη από την πιθανότητα η κοσμική ακτινοβολία να κάνει έναν υπολογιστή να κάνει λάθος καθώς τρέχει έναν 'σωστό' αλγόριθμο. Το αν θα θεωρήσουμε έναν αλγόριθμο να μην είναι ικανοποιητικός για τον πρώτο λόγο και όχι για τον δεύτερο είναι η διαφορά μεταξύ των μαθηματικών και της μηχανικής." Hal Abelson και Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2 Αρχειοθετήθηκε 2006-09-03 στο Wayback Machine..

[4] Hoare, C. A. R. (July 1961). «Algorithm 64: Quicksort» (στα αγγλικά). Communications of the ACM 4 (7): 321. doi:10.1145/366622.366644. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/366622.366644.

[5] Hoare, C. A. R. (July 1961). «Algorithm 65: find» (στα αγγλικά). Communications of the ACM 4 (7): 321–322. doi:10.1145/366622.366647. ISSN 0001-0782. https://dl.acm.org/doi/10.1145/366622.366647.

[6] Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973). «Time bounds for selection» (στα αγγλικά). Journal of Computer and System Sciences 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9. https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339.

[7] Williams, H. C.; Shallit, J. O. (1994), «Factoring integers before computers», στο: Gautschi, Walter, επιμ., Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, 48, Amer. Math. Soc., Providence, RI, σελ. 481–531, doi:10.1090/psapm/048/1314885 ; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".

[8] Berlekamp, E. R. (1971). «Factoring polynomials over large finite fields». Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 (στα Αγγλικά). Los Angeles, California, United States: ACM Press. σελ. 223. ISBN 9781450377867.

[:0-9] 9,0 ^9,1 ^9,2 ^9,3 ^9,4 ^9,5 Knuth, Donald E. (1998). The art of computer programming, volume 3: sorting and searching (2η έκδοση). USA: Addison Wesley Longman Publishing Co., Inc. σελίδες 536–549. ISBN 978-0-201-89685-5.

[10] Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03

[11] Konheim, Alan G.; Weiss, Benjamin (November 1966). «An Occupancy Discipline and Applications». SIAM Journal on Applied Mathematics 14 (6): 1266–1274. doi:10.1137/0114101. ISSN 0036-1399. http://dx.doi.org/10.1137/0114101.

[12] Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). «Universal classes of hash functions» (στα αγγλικά). Journal of Computer and System Sciences 18 (2): 143–154. doi:10.1016/0022-0000(79)90044-8. ISSN 0022-0000.

[13] Bloom, Burton H. (July 1970). «Space/time trade-offs in hash coding with allowable errors». Communications of the ACM 13 (7): 422–426. doi:10.1145/362686.362692. ISSN 0001-0782. http://dx.doi.org/10.1145/362686.362692.

[14] Aragon, C.R.· Seidel, R.G. (Οκτωβρίου 1989). «Randomized search trees». 30th Annual Symposium on Foundations of Computer Science. σελίδες 540–545. ISBN 0-8186-1982-1.

[15] Pugh, William (1989). Concurrent Maintenance of Skip Lists (Τεχνική αναφορά). Dept. of Computer Science, U. Maryland. CS-TR-2222.

[:1-16] 16,0 ^16,1 Alon, Noga (2016). The probabilistic method. Joel H. Spencer (Fourth έκδοση). Hoboken, New Jersey. ISBN 978-1-119-06195-3.

[17] P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR8,479d; Zentralblatt 32,192.

[18] Erdös, P. (1959). «Graph Theory and Probability» (στα αγγλικά). Canadian Journal of Mathematics 11: 34–38. doi:10.4153/CJM-1959-003-9. ISSN 0008-414X. https://archive.org/details/sim_canadian-journal-of-mathematics_1959_11_1/page/34.

[19] Seidel R. Backwards Analysis of Randomized Geometric Algorithms.

[20] A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.

[21] Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834 . For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.

[22] Dyer, M.; Frieze, A.; Kannan, R. (1991), «A random polynomial-time algorithm for approximating the volume of convex bodies», Journal of the ACM 38 (1): 1–17, doi:10.1145/102782.102783, http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf

[23] Füredi, Z.; Bárány, I. (1986), «Computing the volume is difficult», Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986), New York, NY: ACM, σελ. 442–447, doi:10.1145/12130.12176, ISBN 0-89791-193-8, https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf

[24] Shamir, A. (1992), «IP = PSPACE», Journal of the ACM 39 (4): 869–877, doi:10.1145/146585.146609

[25] Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), «Programmability of chemical reaction networks», στο: Condon, Anne; Harel, David; Kok, Joost N. και άλλοι, επιμ., Algorithmic Bioprocesses, Natural Computing Series, Springer-Verlag, σελ. 543–584, doi:10.1007/978-3-540-88869-7_27, https://authors.library.caltech.edu/26121/1/etr090.pdf .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]