Elementar

Im Computerkomplexitätstheorie, das Komplexitätsklasse Elementar von elementare rekursive Funktionen ist die Vereinigung der Klassen

Der Name wurde von geprägt von László Kalmár, im Zusammenhang mit rekursive Funktionen und Unentscheidbarkeit; Die meisten Probleme darin sind alles andere als elementar. Einige natürliche rekursive Probleme liegen außerhalb der Elementar und sind dies so Nicht Elementär. Vor allem gibt es primitive rekursiv Probleme, die nicht in elementarer Weise sind. Wir wissen

Niedrigere Elementär ⊊ Nachfolger ⊊ Elementary ⊊ PrR

Während Elementary begrenzte Anwendungen von enthält Exponentiation (zum Beispiel, ), Pr erlaubt allgemeiner Hyperoperatoren (zum Beispiel, Tetation) die nicht in elementarem enthalten sind.

Definition

Die Definitionen der elementaren rekursiven Funktionen sind die gleichen wie für primitive rekursive Funktionenaußer dass die primitive Rekursion durch begrenzte Summierung und begrenztes Produkt ersetzt wird. Alle Funktionen arbeiten über die natürliche Zahlen. Die grundlegenden Funktionen, die alle elementare rekursiv sind, sind:

  1. Nullfunktion. Gibt Null zurück: f(x) = 0.
  2. Nachfolgerfunktion: f(x) = x + 1. Oft wird dies durch bezeichnet S, wie in S(x). Durch die wiederholte Anwendung einer Nachfolgerfunktion kann man eine Ergänzung erreichen.
  3. Projektionsfunktionen: Diese werden verwendet, um Argumente zu ignorieren. Zum Beispiel, f(a, b) = a ist eine Projektionsfunktion.
  4. Subtraktionsfunktion: f(x, y) = xy wenn y < x, oder 0 wenn yx. Diese Funktion wird verwendet, um Bedingungen und Iteration zu definieren.

Aus diesen grundlegenden Funktionen können wir andere elementare rekursive Funktionen erstellen.

  1. Komposition: Anwenden von Werten aus einer elementaren rekursiven Funktion als Argument auf eine andere elementare rekursive Funktion. Im f(x1, ..., xn) = h(g1(x1, ..., xn), ..., gm(x1, ..., xn)) ist elementar rekursiv, wenn h ist elementar rekursiv und jeder gi ist elementar rekursiv.
  2. Begrenzte Summierung: ist elementar rekursiv, wenn g ist elementar rekursiv.
  3. Begrenztes Produkt: ist elementar rekursiv, wenn g ist elementar rekursiv.

Basis für Elementary

Die Klasse der Elementarfunktionen fällt mit dem Verschluss in Bezug auf die Zusammensetzung der Projektionen und eines der folgenden Funktionssätze zusammen: , , , wo ist die oben definierte Subtraktionsfunktion.[1][2]

Niedrigere elementare rekursive Funktionen

Niedrigere elementare rekursiv Funktionen folgen den Definitionen wie oben, außer dass das begrenzte Produkt nicht zugelassen ist. Das heißt, eine niedrigere elementare rekursive Funktion muss eine Null-, Nachfolger- oder Projektionsfunktion, eine Zusammensetzung anderer geringerer elementare rekursive Funktionen oder die begrenzte Summe einer anderen niedrigeren elementaren rekursiven Funktion sein.

Niedrigere elementare rekursive Funktionen werden auch als Skolem -Elementarfunktionen bezeichnet.[3][4]

Während elementare rekursive Funktionen möglicherweise mehr als exponentielles Wachstum aufweisen, weisen die niedrigeren elementaren rekursiven Funktionen ein Polynomwachstum auf.

Die Klasse der niedrigeren Elementarfunktionen hat eine Beschreibung in Bezug auf die Zusammensetzung einfacher Funktionen, die für elementare Funktionen analog sind.[4][5] Eine polynomisch gebundene Funktion ist nämlich nur dann niedriger, wenn sie unter Verwendung einer Zusammensetzung der folgenden Funktionen ausgedrückt werden kann: Projektionen, , , , , , eine exponentielle Funktion ( oder ) mit der folgenden Einschränkung der Struktur von Formeln: Die Formel kann in Bezug auf einen Exponenten nicht mehr als zwei Etagen haben (zum Beispiel, hat 1 Etage, hat 2 Etagen, hat 3 Stockwerke). Hier ist bitweise und von n und m.

Beschreibende Charakterisierung

Im Beschreibende Komplexität, Elementary ist gleich der Klasse Ho von Sprachen das kann durch eine Formel von beschrieben werden Logik höherer Ordnung.[6] Dies bedeutet, dass jede Sprache in der Klasse Elementary Complexity als eine Formel höherer Ordnung entspricht, die für die Elemente in der Sprache und nur für die Elemente der Sprache gilt. Etwas präziser, , wo ⋯ einen Turm von angibt i Exponentien und ist die Klasse von Abfragen, die mit existenziellen Quantifizierern von beginnen iDie Ordnung und dann eine Formel von (i- 1)th Order.

Siehe auch

Anmerkungen

  1. ^ Mazzanti, S (2002). "Einfache Basen für Klassen primitiver rekursiver Funktionen". Mathematische Logik vierteljährlich. 48: 93–104. doi:10.1002/1521-3870 (200201) 48: 1 <93 :: Aid-Malq93> 3.0.co; 2-8.
  2. ^ S. S. MARCHENKOV, "Überlagerungen elementarer arithmetischer Funktionen", Journal of Applied and Industrial Mathematics, September 2007, Band 1, Ausgabe 3, S. 351-360, doi:10.1134/s1990478907030106.
  3. ^ Th. Skolem"Beweis einiger Theoreme bei rekursiv aufzählbaren Mengen", Notre Dame Journal of Formal Logic, 1962, Band 3, Nummer 2, S. 65-74, doi:10.1305/ndjfl/1093957149.
  4. ^ a b S. A. Volkov, "über die Klasse der Skolem -Elementarfunktionen", Journal of Applied and Industrial Mathematics, 2010, Band 4, Ausgabe 4, S. 588-599, doi:10.1134/s1990478910040149.
  5. ^ Volkov, Sergey (2016). "Endliche Grundlagen in Bezug auf die Überlagerung in Klassen elementarer rekursiver Funktionen [Dissertation]". Arxiv:1611.04843.
  6. ^ Lauri Hella und José María Turull-Torres (2006), "Berechnung von Abfragen mit Logik höherer Ordnung", Theoretische Informatik, 355 (2): 197–214, doi:10.1016/j.tcs.2006.01.009, ISSN 0304-3975

Verweise