Welche Ergebnisse in der Komplexitätstheorie nutzen Uniformität wesentlich?

21

Ein Komplexitätsklassentrennungsbeweis verwendet die Einheitlichkeit von Komplexitätsklassen im Wesentlichen dann, wenn der Beweis das Ergebnis für eine ungleichmäßige Version nicht beweist. Beispielsweise verwenden Beweise, die auf Diagonalisierung basieren (wie Zeit- und Raumhierarchiesätze), die Einheitlichkeit wesentlich, da sie zur Simulation der Programme in erforderlich sind die kleinere Klasse.

Welche Ergebnisse in der Komplexitätstheorie (außer Diagonalisierungsnachweisen) verwenden im Wesentlichen die Einheitlichkeit?

Kaveh
quelle
Es scheint, dass wir kein solches Ergebnis kennen, also scheint es, dass Joshua Grochows Antwort richtig ist. Andererseits fand ich die Arbeit in Andy Duckers Antwort interessant, daher akzeptiere ich seine Antwort, obwohl sie diagonalisiert ist.
Kaveh

Antworten:

6

Wir vermuten, dass Permanent Schaltungen mit Superpolynomgröße benötigt (entweder im arithmetischen oder im booleschen Modell). Wenn wir jedoch Boolesche Schaltkreise mit Schwellwertgattern betrachten, können wir derzeit Superpoly-Untergrenzen nur bei tiefenbeschränkten, einheitlichen Schaltkreisen nachweisen. Ich glaube, die jüngste Referenz für Ergebnisse dieser Art ist

"Ein Superpolynom unterer Grenzwert für die Größe gleichförmiger nichtkonstanter Grenzwertschaltungen für die bleibende Spannung" von Koiran und Perifel.

(Ihr Beweis beinhaltet irgendwann eine Diagonalisierung, so dass dies nicht genau Ihrem Kriterium entspricht, aber ich dachte, es könnte immer noch von Interesse sein.)

Andy Drucker
quelle
Hier ist ein Link zu Koiran und Perifel Papier auf arXive.
Kaveh
11

Ich habe im Wesentlichen vielen Experten diese Frage gestellt, und die Antwort, die ich immer bekomme, lautet: Keine. Diagonalisierungsbeweise verwenden offensichtlich Gleichförmigkeit, und diese bilden den Kern der Zeit- und Raumhierarchiesätze sowie der Fortnow-Williams-Art der Zeit-Raum-Untergrenzen. Soweit mir bekannt ist, scheinen alle anderen uns bekannten Untergrenzen, sowohl für die Trennung von Komplexitätsklassen als auch für Datenstrukturen, nicht einheitlich zu sein. Es wäre toll zu hören, dass ich mich irre :).

Joshua Grochow
quelle
3

Dies ist nur ein Streitpunkt, aber wie Sie in Ihrer Frage anspielen, ist es die Simulation, die Gleichmäßigkeit erfordert, nicht die Diagonalisierung an sich. Wenn ich also Ihre Frage verstehe, würde das auch so etwas wie den Satz von Savitch beinhalten, der Simulation, aber keine Diagonalisierung verwendet. Umgekehrt könnten Sie hypothetisch eine Diagonale haben, die keine Simulation verwendet. (Ich weiß nicht, ob das von praktischem Nutzen ist, aber ich weiß, dass in dieser Hinsicht einige Arbeiten durchgeführt wurden, einschließlich eines klassischen Papiers von Kozen.)

Kurt
quelle
Welche der klassischen Zeitungen von Kozen meinen Sie?
András Salamon
2
Der Kozen-Artikel ist "Indexing of subrecursive classes" ( portal.acm.org/citation.cfm?id=804358 ). Vielleicht möchten Sie auch einen Blick auf "Universal Languages ​​and the Power of Diagonalization" von Nash, Impagliazzo und Remmel werfen ( nashalan.com/ccc03-diag2.pdf ).
Kurt
2
Danke für die Hinweise! Ich habe vor ein paar Tagen die Journalversion der Kozen-Zeitung gelesen
András Salamon
3

TC0

NC1 TC0

Kaveh
quelle
3
Soweit ich weiß, verwendet der Beweis schließlich eine Diagonalisierung. Der Beweis setzt die Negation dessen voraus, was wir beweisen wollen, und kommt dann zu dem Schluss, dass P = EXP, was falsch ist, weil sie durch Diagonalisierung getrennt werden können.
Robin Kothari