In der Theorie der rechnerischen Komplexität sind die Blum-Axiome oder die Blum-Komplexitätsaxiome Axiome, die wünschenswerte Eigenschaften von Komplexitätsmaßen für die Menge der berechenbaren Funktionen angeben. Die Axiome wurden erstmals 1967 von Manuel Blum definiert. [1]
Wichtig ist, dass Blums Satz und der Gap-Satz für jedes Komplexitätsmaß gelten, das diese Axiome erfüllt. Die bekanntesten Maßnahmen, die diese Axiome erfüllen, sind Zeit (d. H. Laufzeit) und Platz (d. H. Speicherauslastung).
Definitionen [ edit
Ein Blum-Komplexitätsmaß ist ein Paar mit ] Gödel-Nummerierung der teilweise berechenbaren Funktionen und eine berechenbare Funktion
was die folgenden Bedingungen erfüllt Blum-Axiome . Wir schreiben für den Teil i Rechenbare Funktion unter der Gödel-Nummerierung und für die teilweise berechenbare Funktion .
![] Phi (i)](https://wikimedia.org/api/rest_v1/media/math/render/svg/640bc704f375a6545a75342fbb8c22bd655f8176)
- die Domänen von und sind identisch.
- der Satz ist rekursiv.
Beispiele [ edit ]
- ist ein Komplexitätsmaß, wenn entweder die Zeit oder der Speicher (oder eine geeignete Kombination davon) ist, die für das System erforderlich ist Berechnung codiert von i
- ist nicht ein Komplexitätsmaß, da das zweite Axiom nicht erfolgreich ist
Hinweise [ edit ]
Ein Blum-Komplexitätsmaß wird mithilfe von berechenbaren Funktionen ohne Bezug auf ein bestimmtes Berechnungsmodell definiert. Um die Definition leichter zugänglich zu machen, formulieren wir die Blum-Axiome in Bezug auf Turing-Maschinen:
A Blum-Komplexitätsmaß ist eine Funktion aus Paaren (Turing-Maschine
- ist dann und nur dann endlich, wenn hält an
- Es gibt einen Algorithmus, der bei Eingabe entscheidet, ob
Als Beispiel sei M auf x simulieren kann, während ihre Schritte gezählt werden. Wenn M die Schritte von n überschreitet, kann es stehen bleiben und zurückweisen, so dass es nicht erforderlich ist, festzustellen, ob M auf x stehen bleibt.
Komplexitätsklassen [ edit ]
Für eine insgesamt berechenbare Funktion f "/> [19456583] "/> [19456583] berechenbare Funktionen können als definiert werden
19659021]) | x . 19 i ( x ) ≤ f x [19659598]] [19659538] ]. { displaystyle C (f): = { varphi _ {i} in mathbf {P} ^ {(1)} | forall x. Phi _ {i} (x) leq f (x) }}
ist das Menge aller berechenbaren Funktionen mit einer Komplexität von weniger als . booleschen Funktionen mit einer Komplexität von weniger als . Wenn wir diese Funktionen als Indikatorfunktionen auf Mengen betrachten, kann als eine Komplexitätsklasse von Mengen betrachtet werden.
![C ^ {0} (f) [19659013] ist die Menge aller <a href=](https://wikimedia.org/api/rest_v1/media/math/render/svg/b5ab1817b5dd59e4e410bdc75256ca13dff85baa)
booleschen Funktionen mit einer Komplexität von weniger als Referenzen [ edit ]
No comments:
Post a Comment