Untere Schranken beweisen durch obere Schranken beweisen

29

Das kürzliche bahnbrechende Ergebnis von Ryan Williams zur Prüfung der Schaltungskomplexität in Bezug auf die Untergrenze bietet eine Beweismethode, bei der das Ergebnis der Obergrenze zum Nachweis der Komplexität in Bezug auf die Untergrenze verwendet wird. Suresh Venkat in seiner Antwort auf diese Frage: Gibt es kontraintuitive Ergebnisse in der theoretischen Informatik? lieferte zwei Beispiele für die Festlegung von Untergrenzen durch den Nachweis von Obergrenzen.

  • Was sind die anderen interessanten Ergebnisse für den Nachweis von Komplexitätsuntergrenzen, die durch den Nachweis von Komplexitätsobergrenzen erhalten wurden?

  • P N PNPP/polyPNP

Mohammad Al-Turkistany
quelle
Sollte dies ein CW sein?
Mohammad Al-Turkistany
Ich mag es so wie es ist (nicht CW), aber ich glaube es ist ein [soft-question].
MS Dousti
2
@Sadeq: denke nicht, dass dies eine weiche Frage ist, das ist präzise genug, um eine klare Antwort zu haben.
Kaveh,
Meyers von Suresh herausgestelltes Ergebnis zeigt, dass die Existenz von Polynomkreisen für P N P beweisen würde . EXPPNP
Mohammad Al-Turkistany

Antworten:

23

Man könnte die Frage umdrehen und fragen, welche Untergrenzen nicht durch den Nachweis einer Obergrenze bewiesen werden. Nahezu alle unteren Grenzen der Kommunikationskomplexität (und die unteren Grenzen des Streaming-Algorithmus und die unteren Grenzen der Datenstruktur, die auf Argumenten der Kommunikationskomplexität beruhen) werden durch den Nachweis bewiesen, dass ein Kommunikationsprotokoll konstruktiv in ein Codierungsschema umgewandelt werden kann, wobei die Länge der Codierung von dem abhängt Die Kommunikationskomplexität des Protokolls und die Untergrenze für das Protokoll ergeben sich aus der Tatsache, dass Sie nicht alle n-Bit-Nachrichten mit n-1 Bits oder weniger codieren können.

Die unteren Grenzen der Razborov-Smolensky-Schaltung zeigen, wie Schaltungen mit begrenzter Tiefe durch Polynome niedrigen Grades simuliert werden können.

Ein paar Kandidaten für untere Schranken, die nicht mit einer oberen Schranke bewiesen werden, könnten der Zeithierarchiesatz sein (obwohl man, um die engsten Schranken zu erhalten, eine effiziente universelle Turing-Maschine benötigt, die eine nicht triviale algorithmische Aufgabe ist) und der Beweis von AC0-Untergrenzen unter Verwendung des Vermittlungs-Lemmas (aber der sauberste Beweis des Vermittlungs-Lemmas verwendet eine Zählung / Inkomprimierbarkeit / Kolmogorov-Komplexität)

Luca Trevisan
quelle
1
Interessant, das ist eine großartige Zusammenfassung der unteren Grenzen der Kommunikationskomplexität! Ein anderer (ungerader?) Kandidat: Ladners Satz / Diagonalisierung. Die Grenzen sind natürlich nicht spezifiziert (noch nicht einmal die Probleme!), Aber es gibt eine Superpolynom-Untergrenze für ein Problem. Dies setzt natürlich P NP voraus , was möglicherweise mit einer oberen Schranke, a la GCT, bewiesen werden könnte ...
Daniel Apon,
14

In seltsamer Weise ist das PCP-Theorem selbst ein gutes Beispiel für den Nachweis einer Untergrenze über eine Obergrenze. Eine "effiziente" randomisierte Strategie zum Verifizieren eines Beweises unter Verwendung einer konstanten Anzahl von Prüfpunkten des Beweises und nur von zufälligen Bits führt zu einer Untergrenze zum Annähern der Anzahl von erfüllten Klauseln in einer Instanz von 3SAT.Logn

Suresh Venkat
quelle
10
Wenn Sie die NP-Härte (im Gegensatz zur Trennung von einer Klasse) als Untergrenze betrachten, brauchen Sie den PCP-Satz nicht. Reduktionen sind effiziente Algorithmen, die beweisen, dass einige Probleme schwierig sind.
Tsuyoshi Ito
Das ist ein guter Punkt, Tsuyoshi. Reduzierungen der NP-Härte sind jedoch "direkt". Zeigen Sie, dass das Lösen eines unbekannten Problems ein bekanntes schweres Problem löst. Einige der hier aufgeführten Beispiele sind indirekter Natur. Aber das ist natürlich subjektiv.
Suresh Venkat
3
Die Aussage des PCP-Theorems ist die NP-Vollständigkeit von Gap-3SAT. Außerdem weiß ich nicht, was Sie damit gemeint haben, dass das PCP-Theorem indirekt ist. Es ist wahr, dass das PCP-Theorem einen der kompliziertesten Beweise für NP-Vollständigkeitsergebnisse erfordert, aber ist es eine gute Sache?
Tsuyoshi Ito
Suresh, könnten Sie bitte hier als neue Antwort eine erweiterte Version der beiden Beispiele posten, auf die Sie in Ihrer Antwort auf die andere Frage (Meyers Ergebnis und GCT) verwiesen haben?
Mohammad Al-Turkistany
irgendein Grund warum? Ich habe kein Problem damit, aber ist es notwendig, da Sie es in der Frage zitieren?
Suresh Venkat
12

Die Inkomprimierbarkeitsmethode basiert auf der Kolmogorov-Komplexität, um untere Schranken zu beweisen. Eine der ersten Anwendungen dieser Methode bestand darin, zu beweisen, dass das Erkennen von Palindromen auf einer Turing-Maschine mit einem einzelnen Band eine quadratische Zeit erfordert.

Die Idee dieser Methode ist es, eine Prozedur zum Finden einer Eingabe unter Verwendung der Informationen zu beschreiben, die in der Ausführung eines Algorithmus enthalten sind, um das Problem zu lösen, das wir bei dieser Eingabe betrachten. Je besser das Verfahren ist, desto höher ist die Untergrenze des ursprünglichen Problems.

Ausführliche Informationen finden Sie natürlich im Lehrbuch von Li und Vitanyi .

Marc
quelle
11

Für die Frage "Untergrenze über Obergrenze" haben Sie Folgendes gestellt:

Das STOC 2010-Papier "Komprimieren interaktiver Kommunikation" [BBCR10] kommt zu einem verbesserten direkten Summensatz für die randomisierte Kommunikationskomplexität, indem ein verbessertes Komprimierungsprotokoll für die interaktive Kommunikation demonstriert wird.

CichO~(Cich)

fnkfkn

Daniel Apon
quelle
7

Das ist irgendwie anders, als Sie es gefragt haben, aber da es damit zusammenhängt, dachte ich, ich könnte es erwähnen.

Carter & Wegman (1977) führten den Begriff des universellen Hashings ein . Der Begriff wurde in zahlreichen Arbeiten ( Sipser (1983) , Stockmeyer (1983) , Babai (1985) und Goldwasser & Sipser (1986) ) verwendet, um ungefähre Untergrenzen zu beweisen .

Dies war bis 1987, als Fortnow das universelle Hashing nutzte , um ungefähre obere Schranken zu beweisen . (In der Tat, um ein Protokoll zum Nachweis der ungefähren oberen Schranken bereitzustellen.)


Bearbeiten:

Dies sind keine Ergebnisse mit einer niedrigeren Grenze, aber sie könnten trotzdem nützlich sein:

NPP/pOlyPH=Σ2p=Π2p

NPP/pOlyEINM=MEIN

cONPNP/pOlyPH=Σ3p=Π3p

MS Dousti
quelle
5

PNP

CC1Cm

PNP

Mohammad Al-Turkistany
quelle
5

Hier ein Beispiel aus der Computational Complexity: Ein moderner Ansatz von Arora und Barak (Seite 128):

EXPO(2n/n)PNP

Mohammad Al-Turkistany
quelle