Αξιώματα Μπλουμ

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

Κυρίως, τα θεωρήματα της Επιτάχυνσης και του Κενού θεωρήματα ισχύουν για οποιοδήποτε μέτρο πολυπλοκότητας που ικανοποιεί τα αξιώματα. Τα πιο γνωστά μέτρα που ικανοποιούν τα αξιώματα είναι εκείνα του χρόνου (δηλαδή, τρέχοντος χρόνου) και του χώρου (δηλαδή, τη χρήση της μνήμης).

Ορισμοί

Ένα μέτρο πολυπλοκότητας Μπλουμ  είναι μια πλειάδα $(\varphi ,\Phi )$ με $\varphi$ μία Γκέντελ αρίθμηση των επιμέρους υπολογίσιμη συναρτήσεων $\mathbf {P} ^{(1)}$ και μία υπολογίσιμη συνάρτηση

$\Phi :\mathbb {N} \to \mathbf {P} ^{(1)}$

η οποία πληροί τα ακόλουθα αξιώματα Μπλουμ. Γράφουμε $\varphi _{i}$ για την i-οστή μερική υπολογίσιμη συνάρτηση στο πλαίσιο της $\varphi$  αρίθμησης Γκέντελ, και $\Phi _{i}$ για τη μερική υπολογίσιμη συνάρτηση $\Phi (i)$.

• τα πεδία ορισμού των $\varphi _{i}$ και $\Phi _{i}$ να είναι πανομοιότυπα.
• το σύνολο $\{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}$ να είναι αναδρομικό.

Παραδείγματα

• $(\varphi ,\Phi )$ είναι ένα μέτρο πολυπλοκότητας, αν $\Phi$ είναι είτε ο χρόνος ή η μνήμη (ή κάποιος κατάλληλος συνδυασμός τους) που απαιτείται για τον υπολογισμό που κωδικοποιείται από το i.
• $(\varphi ,\varphi )$ δεν είναι ένα μέτρο πολυπλοκότητας, δεδομένου ότι αποτυγχάνει το δεύτερο αξίωμα.

Σημειώσεις

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

Ένα μέτρο πολυπλοκότητας Μπλουμ είναι μια συνάρτηση $\Phi$ από ζεύγη (μηχανή Τιούρινγκ $M$, εισαγωγή $x$ για $M$) για τους φυσικούς αριθμούς σε ένωση με το άπειρο. Επιπλέον, η $\Phi$ θα πρέπει να ικανοποιεί τα ακόλουθα αξιώματα:

• $\Phi (M,x)$ είναι πεπερασμένη αν και μόνο αν $M(x)$ τερματίζει
• Υπάρχει ένας αλγόριθμος που, για εισαγωγή $(M,x,n)$ αποφασίζει αν $\Phi (M,x)=n$

Για παράδειγμα, ας υποθέσουμε ότι η $\Phi (M,x)$ δίνει τον αριθμό των χρονικών βημάτων που η μηχανή M τρέχει για είσοδο x πριν την ανάσχεση. Το πρώτο αξίωμα είναι σαφές, το δεύτερο ακολουθεί, διότι μια καθολική μηχανή Τιούρινγκ μπορεί να προσομοιώσει M στο x , ενώ μετράει τα βήματά της. Αν η M υπερβαίνει τα n βήματα, μπορεί να τερματίσει και να απορρίψει, έτσι δεν υπάρχει καμία ανάγκη να προσδιοριστεί αν η M σταματά στο x.

Κλάσεις πολυπλοκότητας

Για μια ολική υπολογίσιμη συνάρτηση $f$ κλάσεων πολυπλοκότητας των υπολογίσιμων συναρτήσεων μπορεί να οριστεί ως

$C(f):=\{\varphi _{i}\in \mathbf {P} ^{(1)}|\forall x.\ \Phi _{i}(x)\leq f(x)\}$

$C^{0}(f):=\{h\in C(f)|\mathrm {codom} (h)\subseteq \{0,1\}\}$

$C(f)$ είναι το σύνολο όλων των υπολογίσιμων συναρτήσεων με μια πολυπλοκότητα μικρότερη από την $f$. $C^{0}(f)$ είναι το σύνολο όλων των Μπούλιαν-αποτιμώμενων συναρτήσεων με μια πολυπλοκότητα μικρότερη από την $f$. Αν λάβουμε υπόψη αυτές τις συναρτήσεις ως δείκτες συναρτήσεων στα σύνολα, $C^{0}(f)$ μπορεί να θεωρηθεί ως μια κλάση πολυπλοκότητας των συνόλων.