Κάναμε μια μικρή εισαγωγή στο μάθημα με διάφορα παραδείγματα.
Μιλήσαμε κατ' αρχήν για το πρόβλημα του να αποφασίσουμε αν ένας αριθμός $n$ είναι πρώτος ή όχι. Είδαμε ότι παρ' ότι μόλις πριν από λίγα χρόνια βρέθηκε αλγόριθμος με χρόνο πολυωνυμικό ως προς το μέγεθος του input (εδώ το input είναι το n που έχει μέγεθος, όταν το γράψει κανείς κάτω με ψηφία, $\log n$) ακόμη χρησιμοποιούνται στην πράξη κάποιοι πιο γρήγοροι πιθανοθεωρητικοι αλγόριθμοι (που έχουν δηλ. μια μικρή πιθανότητα να δώσουν λάθος αποτέλεσμα). Μια περιγραφή αυτών των πιθανοθεωρητικών αλγορίθμων μπορείτε να δείτε εδώ (δεν μπήκαμε σε λεπτομέρεια καθόλου).
Το επόμενο μας παράδειγμα ήταν το εξής: κάποιος μας δίνει δύο πολυώνυμα γραμμένα σε μορφή γινομένων το καθένα με πολλούς πολυωνυμικούς παράγοντες, π.χ., μας δίνει κάποιος τα δύο πολυώνυμα $$ A(x) = (2x+1)(x^2-3)(4+5x^7)(3x^5-4x^4-3)\cdots \text{ και } B(x) = (3x-2)(5x^2-4)(x^3+x^7) \cdots, $$ και πρέπει να αποφασίσουμε αν είναι ίσα. Ας υποθέσουμε ότι και δύο πλευρές έχουν βαθμό $\le N$. Αν μας είχαν δώσει τα δύο πολυώνυμα σε ανεπτυγμένη μορφή ($a_N x^N + a_{n-1}x^{N-1}+\cdots+a_0$) τότε θα ήταν εύκολο να αποφασίσουμε συγκρίνοντας ένα προς ένα τα μονώνυμα. Αυτό θα μας έπαιρνε χρόνο $O(N)$ (υποθέτουμε εδώ ότι οι αλγεβρικές πράξεις μας κοστίζουν μια μονάδα χρόνου). Όμως το να μετατρέψουμε τα δύο πολυώνυμα σε ανεπτυγμένη μορφή μπορεί να μας κοστίσει πολύ. Φανταστείτε ότι έχουμε π.χ. $N/2$ παράγοντες και καθένας από αυτούς έχει τουλάχιστον 2 προσθετέους. Τότε αν κανείς εφαρμόσει την επιμεριστική ιδιότητα μπορεί να καταλήξει κανείς με εκθετικό ($2^N$) πλήθος προσθετέων (τους οποίους θα πρέπει μετά να "μαζέψει". Αν είναι κανείς προσεκτικός μπορεί να το κάνει με $O(N^2)$ πράξεις.
Ο αλγόριθμος που χρησιμοποιούμε είναι ο εξής: παίρνουμε τυχαία το $x$ να είναι ένα από τα στοιχεία του συνόλου $\{1, 2, \ldots, 2N\}$ και υπολογίζουμε το $D = A(x)-B(x)$. Αν προκύψει $D \neq 0$ τότε απαντάμε ότι τα δύο πολυώνυμα δεν είναι ίσα. Αλλιώς απαντάμε ότι είναι.
Προφανώς υπάρχει πιθανότητα να έχουμε απαντήσει λάθος αν πούμε ότι είναι ίσα. Αυτό συμβαίνει αν $x$ τύχει να είναι ρίζα του πολυωνύμου $A(x)-B(x)$ χωρίς αυτό το πολυώνυμο να είναι το μηδενικό. Όμως το πολυώνυμο $A(x)-B(x)$ έχει βαθμός $\le N$ άρα έχει το πολύ $N$ ρίζες, οπότε η πιθανότητα να κάνουμε λάθος είναι το πολύ $1/2$. Εύκολα βλέπουμε ότι ο χρόνος που παίρνει αυτός ο αλγόριθμος είναι μόνο $O(N)$, μια και το μόνο που χρειάζεται να κάνουμε είναι να υπολογίσουμε τα πολυώνυμα στη μορφή που μας δίνονται, χωρίς να χρειαστεί να τα μετατρέψουμε σε άλλη μορφή.
Αν θέλουμε να ελαττώσουμε κι άλλο την πιθανότητα σφάλματος τότε δεν έχουμε παρά να τρέξουμε το προηγούμενο $k$ φορές, οπότε η πιθανότητα να κάνουμε λάθος όλες τις $k$ φορές είναι $\le 2^{-k}$ (αν έστω και μια φορά βρούμε $D \neq 0$ τότε είμαστε σίγουροι ότι $A \neq B$).
Ας πούμε ότι κάποιος μας δίνει τρεις $N\times N$ πίνακες $A, B, C$ και ισχυρίζεται ότι $A B = C$. Εμείς πρέπει αν ελέγξουμε αυτό τον ισχυρισμό. Ένας τρόπος θα ήταν να υπολογίσουμε το γινόμενο $AB$ και να συγκρίνουμε το αποτέλεσμα με τον πίνακα $C$. Όμως αυτό παίρνει πολύ χρόνο $O(N^3)$ μια και πρέπει να υπολογίσουμε τις $N^2$ ποσότητες $$ (AB)_{i,j} = \sum_{k=1}^N A_{i,k} B_{k, j}, $$ κάθε μια από τις οποίες θέλει $O(N)$ πράξεις για να υπολογιστεί.
Αντί αυτού χρησιμοποιούμε τον παρακάτω πιθανοθεωρητικό αλγόριθμο:
Παίρνουμε $x$ να είναι ένα τυχαίο διάνυμσα μήκους $N$ με στοιχεία 0 ή 1. Με άλλα λόγια το $x$ αντλείται από το σύνολο $$ \{0, 1\}^N $$ με την ομοιόμορφη κατανομή.
Υπολογίζουμε έπειτα τη διαφορά $ABx-Cx$ και αν αυτή βγεί το μηδενικό διάνυσμα απαντάμε ότι $AB=C$ αλλιώς ότι $AB \neq C$.
Προφανώς μπορεί να κάνουμε λάθος στην περίπτωση που απαντάμε $AB=C$ (αλλά όχι φυσικά στην άλλη περίπτωση). Δείχνουμε τώρα ότι η πιθανότητα λάθους είναι το πολύ $1/2$.
Ας υποθέσουμε ότι $D=AB-C$ δεν είναι ο μηδενικός πίνακας οπότε πρέπει κάποιο στοιχείο του $D$, έστω το $D_{11}$, να είναι $\neq 0$. Ας είναι τότε $x$ ένα στοιχείο του $\{0, 1\}^N$ τέτοιο ώστε $Dx=0$. Στο "κακό" αυτό $x$ (που μας κάνει να απαντάμε λάθος) αντιστοιχούμε τώρα ένα άλλο στοιχείο του $\{0, 1\}^Ν$ το $x'$ που έχει ακριβώς τις ίδιες συντεταγμένες με το $x$ εκτός από το $x_1'$ που είναι διαφορετικό από το $x_1$. Τότε εύκολα βλέπουμε ότι $$ (Dx)_1-(Dx')_1 = \sum_{k=1}^N D_{1k}x_k - \sum_{k=1}^N D_{1k}x_k' = D_{11}(x_1-x_1') \neq 0. $$ Άρα δε γίνεται να έχουμε και $Dx' = 0$ οπότε για κάθε "κακό" $x$ έχουμε βρει ένα "καλό" $x'$ και αυτή η αντιστοίχιση είναι 1-1. Αυτό σημαίνει ότι τα καλά στοιχεία του $\{0, 1\}^N$ είναι τουλάχιστον όσα και τα κακά, οπότε η πιθανότητα να έχουμε επιλέξει ένα κακό $x$ είναι το πολύ $1/2$ και αυτή είναι το πολύ και η πιθανότητα σφάλματος του αλγορίθμου μας.
Όπως και στον αλγόριθμο για τον έλεγχο ισότητας πολυωνύμων μπορούμε επαναλαμβάνοντας τον αλγόριθμό μας $k$ φορές να μειώσουμε την πιθανότητα σφάλματος σε $2^{-k}$.
Αυτό κάνουμε στον κώδικα που δείχνουμε παρακάτω (το $k$ είναι η μεταβλητή trials).
import numpy as np # Βιβλιοθήκη numpy για να διευκολύνουμε πράξεις με πίνακες και διανύσματα
import time # Βιβλιοθήκη time για να χρονομετράμε διάφορα κομμάτια του κώδικά μας
N = 2000 # Οι πίνακές μας θα είναι διάστασης NxN
trials = 10 # Τόσες φορές θα επαναλάβουμε το πείραμά μας
equal = True # δείχνει αν θεωρούμε ότι AB=C
A = np.random.rand(N, N) # Φτιάχνουμε τυχαίο πίνακα NxN με στοιχεία ομοιόμορφα στο [0, 1]
B = np.random.rand(N, N) # Ομοίως με το A
t1 = time.time() # μαρκάρουμε την αρχή του χρόνου σε sec
C = A.dot(B) # υπολογίζουμε C = A B
t2 = time.time() # τέλος του χρόνου
print(f"Took {t2-t1} seconds to multiply the matrices") # πόσο χρόνο μας πήρε να πολλαπλασιάσουμε AB
D = C # αντίγραφο του πίνακα C
D[N//2][N//2] += 1e-2 # το πειράζουμε σε μια θέση προσθέτοντάς του μια τιμή (περίπου στο μέσο του πίνακα)
t1 = time.time() # αρχή χρόνου
for i in range(trials): # επαναλαμβάνουμε trials φορές το πείραμα
x = np.random.randint(0, 2, size=N) # x είναι τυχαίο διάνυσμα μήκους n με στοιχεία 0 ή 1
y = B.dot(x) # y = Bx
z = A.dot(y) # z = Ay
zz = D.dot(x) #zz = Dx
dist = np.linalg.norm(z-zz) # νόρμα της διαφοράς των διανυσμάτων Dx και ABx
if dist>1e-6: # αν μεγάλη διαφορά θεωρούμε τα διανύσματα διαφορετικά
print(f"Not equal. Norm of difference is {dist}") # τυπώνουμε ότι τα βρήκαμα διαφορετικά
equal = False # μαρκάρουμε ότι βρήκαμε διαφορά στα διανύσματα και σταματάμε το πείραμα
break
t2 = time.time() # τέλος χρόνου
print(f"Took {t2-t1} seconds to check equality") # πόσο χρόνο μας πήρε να ελέγξουμε την ισότητα AB=C
if equal: print("Equal") # αν τα βρήκαμε ίσα το τυπώνουμε