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

Στην θεωρία υπολογιστικής πολυπλοκότητας τα **αξιώματα Μπλουμ** ή **αξιώματα πολυπλοκότητας Μπλουμ** είναι τα αξιώματα που καθορίζουν επιθυμητές ιδιότητες των μέτρων πολυπλοκότητας για το σύνολο των υπολογίσιμων συναρτήσεων. Τα αξιώματα ορίστηκαν πρώτα από τον Εμάνουελ Μπλουμ , το 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) μπορεί να θεωρηθεί ως μια κλάση πολυπλοκότητας των συνόλων.

## Παραπομπές


Κατηγορία:Θεωρία υπολογισμού