Komplexitätsergebnisse für rekursive Funktionen mit niedrigerer Elementarzahl?

Fasziniert von Chris Presseys interessanter Frage zu elementar-rekursiven Funktionen , habe ich mehr untersucht und konnte im Internet keine Antwort auf diese Frage finden.

Die elementaren rekursiven Funktionen entsprechen gut der exponentiellen Hierarchie . $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$

Aus der Definition geht hervor, dass Entscheidungsprobleme, die durch Funktionen mit niedrigeren Elementen entscheidbar sind (Begriff?), In EXP und tatsächlich in DTIME . Diese Funktionen sind auch darauf beschränkt, Zeichenfolgen linear in ihrer Eingabelänge auszugeben [1]. $(2^{O(n)})$

Andererseits sehe ich keine offensichtlichen Untergrenzen; Auf den ersten Blick scheint es denkbar, dass LOWER-ELEMENTARY NP streng enthalten könnte oder vielleicht einige Probleme in P oder höchstwahrscheinlich eine Möglichkeit, die ich mir noch nicht vorgestellt habe, nicht enthält. Es wäre episch cool, wenn LOWER-ELEMENTARY = NP wäre, aber ich nehme an, das ist zu viel verlangt.

Also meine Fragen:

Ist mein Verständnis bisher richtig?
Was ist über die Komplexitätsklassen bekannt, die die unteren elementaren rekursiven Funktionen begrenzen?
(Bonus) Haben wir nette Komplexitätsklassencharakterisierungen, wenn wir weitere Einschränkungen für rekursive Funktionen vornehmen? Ich dachte insbesondere an die Beschränkung auf -gebundene Summierungen, die meiner Meinung nach in Polynomzeit ablaufen und eine lineare Ausgabe erzeugen. oder konstant begrenzte Summierungen, die meiner Meinung nach in Polynomzeit ablaufen und höchstens ausgeben . $\log(x)$ $n + O(1)$

[1]: Wir können (glaube ich) zeigen, dass Funktionen mit niedrigeren Elementaren diesen Einschränkungen durch strukturelle Induktion unterliegen, vorausgesetzt, die Funktionen haben eine Komplexität von und Ausgänge der Bitlänge bei einer Eingabe der Länge . Wenn $h,g_1,\dots,g_m$ $2^{O(n)}$ $O(n)$ $n$ $f(x) = h(g_1(x),\dots,g_m(x))$ Und ließ , jeweils hat Ausgang der Länge , so ein HAS -Länge Eingang (und damit -Länge Ausgang); Die Komplexität der Berechnung aller s ist und von ist , so dass die Komplexität $n := \log x$ $g$ $O(n)$ $h$ $O(n)$ $O(n)$ $g$ $m2^{O(n)}$ $h$ $2^{O(n)}$ $f$ $2^{O(n)}$ und Ausgabe der Länge wie beansprucht. $O(n)$

Wenn , haben die s Ausgänge der Länge , so dass der Wert der Summe der Ausgänge , also hat ihre Summe die Länge . Die Komplexität der Summierung dieser Werte ist durch (die Anzahl der Summierungen) mal $f(x) = \sum_{i=1}^x g(x)$ $g$ $O(n)$ $2^n 2^{O(n)} \in 2^{O(n)}$ $O(n)$ $2^n$ (die Komplexität jeder Addition) ergibt , und die Komplexität der Berechnung der Ausgaben wird durch (die Anzahl der Berechnungen) mal (die Komplexität jeder einzelnen) begrenzt, was ergibt . Also hat die Komplexität und die Ausgabe der Länge wie beansprucht. $O(n)$ $2^{O(n)}$ $2^{n}$ $2^{O(n)}$ $2^{O(n)}$ $f$ $2^{O(n)}$ $O(n)$

cc.complexity-theory reference-request complexity-classes computability usul
quelle

Der Wikipedia-Artikel, auf den Sie verweisen, besagt, dass Funktionen mit niedrigeren Elementaren ein Polynomwachstum aufweisen (es gibt jedoch keinen Hinweis). Es wäre ein guter Schritt, um zu zeigen, dass ein P-vollständiges Problem mit Elementarfunktionen gelöst werden kann oder nicht. Es scheint nicht ohne weiteres unmöglich, eine Turing-Maschine für n Schritte zu simulieren - vielleicht eine begrenzte Summe, die der Anzahl der Schritte einer anderen begrenzten Summe entspricht, die jedem Zustandsübergang entspricht?

Chris Pressey

@Chris - Meine Vermutung war, dass "Polynomwachstum" sich darauf bezieht, dass die Anzahl der Bits in der Ausgabe nicht mehr als linear in der Anzahl der Bits in der Eingabe ist. Ich bin damit einverstanden, dass die Simulation sehr plausibel und in Polynomzeit machbar erscheint (aber möglicherweise einige Details benötigt, um dies zu überprüfen!).

Usul

Entschuldigung, dieser erste Teil ist möglicherweise nicht klar, aber es liegt daran, dass die Ausgabe bei Eingabe des Werts

höchstens einen Polynomwert in

x

$x$

x

$x$

Usul

Zu Frage 3: Die in der Variante mit

-gebundener Summierung definierbaren Funktionen liegen alle in der Komplexitätsklasse einheitlich

. Mit konstant begrenzter Summation erhalten Sie eine Unterklasse der Uniform

\log (x)

$\log(x)$

{T C}^{0}

$\mathsf{TC}^0$

{A C}^{0}

$\mathsf{AC}^0$

Jan Johannsen

@Xoff Ich glaube, es ist alles in der Summierung: Wir summieren von

nach

, wobei (bei einer Eingabe von

Bits)

die Größe

, sodass unsere Summe das

fache der Größe jedes Summanden beträgt.

1

$1$

x

$x$

n

$n$

x

$x$

2^{n}

$2^n$

2^{n}

$2^n$

Usul

"Niedrigere Elementarfunktionen sind in EXP " ist korrekt. Sie befinden sich tatsächlich in DPSPACE ( n ); wie zum Beispiel aus der strukturellen Induktion ersichtlich ist.
Hier wird gezeigt [1], dass die boolesche Erfüllbarkeit SAT in der untersten Ebene E ₀ der Grzegorczyk-Hierarchie liegt, dh mit begrenzter Rekursion anstelle einer begrenzten Summation.

[1] Cristian Grozea: NP-Prädikate, die auf der schwächsten Ebene der Grzegorczyck-Hierarchie (sic!) Berechnet werden können. Journal of Automata, Languages and Combinatorics 9 (2/3) : 269 & ndash; 279 (2004).

Die Grundidee besteht darin, die gegebene Formel der binären Länge n in eine ganze Zahl N mit einem Wert zu codieren, der in n ungefähr exponentiell ist ; und dann die Existenz einer zufriedenstellenden Zuordnung in Bezug auf die durch das N (und nicht durch n ) begrenzte Quantifizierung ausdrücken .

Diese Methode scheint sich von E ₀ auf Lower Elementary zu übertragen
(und für willkürliches, aber festes k von SAT auf QBF _k zu verallgemeinern ).

Es bedeutet nicht , E ₀ enthält NP (oder sogar P für diese Angelegenheit), aber, weil polytime Berechnungen bekannt sind , verlassen E ₂ .

Martin Ziegler
quelle

Komplexitätsergebnisse für rekursive Funktionen mit niedrigerer Elementarzahl?

Antworten: