Bekannteste deterministische Zeitkomplexität untere Schranke für ein natürliches Problem in NP

25

Diese Antwort auf große ungelöste Probleme in der theoretischen Informatik? Frage besagt, dass es offen ist, wenn ein bestimmtes Problem in NP Ω(n2) Zeit erfordert .

Als ich mir die Kommentare unter der Antwort ansah, fragte ich mich:

Was ist, abgesehen von Auffüllen und ähnlichen Tricks, die bekannteste Zeitkomplexität unterer Schranke einer deterministischen RAM-Maschine (oder einer deterministischen Turing-Maschine mit mehreren Bändern) für ein interessantes Problem in NP (das auf natürliche Weise angegeben wird)?

Gibt es ein natürliches Problem in NP, von dem bekannt ist, dass es in quadratisch deterministischer Zeit auf einem vernünftigen Maschinenmodell nicht lösbar ist?

Was ich im Wesentlichen suche, ist ein Beispiel, das den folgenden Anspruch ausschließt:

Jedes natürliche NP-Problem kann in gelöst werden.O(n2)

Kennen wir ein NP-Problem, das dem von Karp aus dem Jahr 1972 oder von Garey und Johnson aus dem Jahr 1979 ähnelt und das eine deterministische Zeit von erfordert ? Oder ist es nach bestem Wissen möglich, dass alle interessanten natürlichen NP-Probleme in O ( n 2 ) deterministischer Zeit gelöst werden können ?Ω(n2)O(n2)

Bearbeiten

Klarstellung, um jegliche Verwirrung zu beseitigen, die sich aus der Nichtübereinstimmung zwischen Untergrenze und Obergrenze ergibt : Ich suche nach einem Problem, von dem wir wissen, dass wir es in nicht lösen können . Wenn ein Problem die stärkere Anforderung erfüllt, dass Ω ( n 2 ) oder ω ( n 2 ) Zeit benötigt wird (für alle Eingänge, die groß genug sind), ist es besser, aber unendlich oft ausreichend.o(n2)Ω(n2)ω(n2)

Anonym
quelle
5
Die einzigen superlinearen Untergrenzen, die ich für natürliche Probleme in NP kenne, sind die Zeit-Raum-Kompromisse für SAT ( dl.acm.org/citation.cfm?doid=1101821.1101822 ) . und sie sagen nichts, wenn der Raum linear sein darf.
Sasho Nikolov
@SashoNikolov, Zeit-Raum-Ergebnisse gelten für SAT, und es gibt keine Reduktion von vielen natürlichen NP-Problemen auf SAT, bei denen die Größe der Ausgabe in Bezug auf die Größe der Eingabe linear begrenzt ist. Ein -Untergrenze für ein natürliches NP-Problem muss für SAT kein stärkeres Ergebnis implizieren als derzeit bekannt. Ω(n2)
Anonym
1
Ich sage, ich kenne keine super lineare Untergrenze für andere natürliche NP-Probleme
Sasho Nikolov
Wie verwendet man das Auffüllen, um ein künstliches Problem in NP mit einer unteren Grenze der -Zeitkomplexität zu erhalten ? Ω(n2)
Robin Kothari
@RobinKothari, nimm ein Problem in DTIME ( ) und fülle es auf. Der Beweis beruht auf dem nicht deterministischen Zeithierarchiesatz, und das Auffüllen war nicht der richtige Weg, um auf das Beispiel zu verweisen. Wir können ein NP-Problem in NTIME ( Ω ( n 2 ) ) direkt annehmen . Ω(2n)Ω(n2)
Anonym

Antworten:

16

Adachi, Iwata und Kasai in einer 1984 JACM Papier Show durch Reduktion , dass die Katze und -Mice Spiel hat eine n Ω ( k ) niedrige Zeit gebunden. Das Problem ist in P für jedes k . Das Problem wird auf einem gerichteten Graphen dargestellt. Die Bewegungen bestehen aus der Katze und dann einem der abwechselnden Schritte der k Mäuse. Die Mäuse gewinnen, wenn sie auf einem bestimmten Käseknoten landen können, bevor die Katze auf ihnen landet. Die Frage ist, ob die Katze einen erzwungenen Gewinn hat. Tatsächlich handelt es sich um ein vollständiges Problem, daher basiert die Untergrenze tatsächlich auf der Diagonalisierung, die die Zeithierarchie ergibt.knΩ(k)kk

Grandjean hat gezeigt, dass die untere Grenze der Pippenger-, Paul-, Szemeredi- und Trotter-Zeit für eine SAT-Codierung gilt, obwohl das Ergebnis von Santhanam diese unter Umständen subsumiert.

Zusätzlich zu den in anderen Kommentaren erwähnten Zeit-Raum-Kompromiss-Untergrenzen für SAT gibt es eine Reihe von Arbeiten zu Verzweigungsprogramm-Untergrenzen, die Zeit-Raum-Kompromisse für Turing-Maschinen implizieren. Für Probleme wie FFT, Sortieren oder Berechnen von universellen Hash-Funktionen gibt es quadratische Kompromissuntergrenzen von Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari, aber diese sind für Funktionen mit vielen Ausgaben. Für Entscheidungsprobleme in P gibt es Zeit-Raum-Kompromiss-Untergrenzen, die für Zeitgrenzen gelten, die aber diese sind schwächer als für SAT bekannt.O(nlogn)

Paul Beame
quelle
Hast du eine Vorstellung von der Beziehung zwischen Katz- und Mausspiel und NP?
vzn
12

Das mir bekannte klassische Ergebnis geht auf Paul, Pippenger, Szemeredi und Trotter (1983) zurück und trennt deterministische von nicht deterministischer linearer Zeit.

Hinzu kommt das bereits erwähnte neuere Ergebnis von Fortnow, Lipton, van Melkebeek und Viglas (2004) . Die Einzigartigkeit dieses Ergebnisses besteht darin, dass es ein Zeit-Raum-Kompromiss ist, der sowohl Raum als auch Zeit begrenzt.

Mir ist jedoch auch ein Ergebnis von Santhanam (2001) bekannt , das eine Untergrenze von ω ( n ) beweist. Dieses Ergebnis ist bei zeitlichen Einschränkungen etwas stärker als das oben genannte, bietet jedoch keine Garantie für den Platzbedarf.ω(nlogn)

Angesichts des oben Gesagten und meiner Kenntnisse auf diesem Gebiet würde ich sagen, dass es ein ziemlich großer Schritt wäre, zu beweisen, dass es ein -vollständiges Problem gibt, das in der deterministischen Zeit von O ( n 2 ) nicht gelöst werden kann . Soweit ich weiß, wird ein solches Ergebnis als höchst nicht trivial angesehen und erfordert wahrscheinlich neue Techniken für die untere Schranke.NPO(n2)

Hinweis: Mein Wortlaut des Problems im letzten Absatz unterscheidet sich von Ihrer Frage. Ich könnte nicht wählerisch sein (und vielleicht auch nicht viel helfen) und Ihnen sagen, dass es in und somit in N P eine unendliche Anzahl von Problemen gibt, die in O ( n 2 ) deterministischer Zeit nicht durch die deterministische Zeit gelöst werden können Hierarchiesatz.PNPO(n2)


Bearbeiten: Nach weiteren Überlegungen können Sie in ein Problem finden , das Ihren Anforderungen entspricht:NP

  1. Jedes natürliche Problem mit einer Untergrenze von , wobei f ( n ) = Ω ( n 2 logDTIME(f(n)) . Nach dem DTIME-Hierarchiesatz benötigt es ω ( n 2 ) Zeit. Ich glaube, es gibt eine Handvoll davon.f(n)=Ω(n2logn)ω(n2)
  2. Jedes natürliche Problem mit einer Untergrenze von , wobei fNTIME(f(n)) , unter Verwendung der NTIME-Hierarchie. Solche natürlichen Probleme sind mir nicht bekannt.f(n)=ω(n2)
  3. Jedes natürliche Problem mit einer Untergrenze von , wobei f ( n ) = ω ( n 2 / log n ) . Dies ist durch die TIME-SPACE-Trennung gerechtfertigt. Ich glaube dasSPACE(f(n))f(n)=ω(n2/logn)

Die obigen unteren Grenzen sollten für die Bitkomplexität des Problems gelten.

Noch einmal, wenn Sie sich auf -vollständige Probleme beschränken, sind mir solche Untergrenzen nicht bekannt.NP

Chazisop
quelle
3
Die Frage stellt sich nach einem natürlichen Problem
Sasho Nikolov
Vielen Dank, aber ich frage nicht nach deterministischer vs. nicht deterministischer Zeit: Sie können jedes Problem in NTIME ( ) annehmen, solange es Ω ( n 2 ) deterministische Zeit erfordert . Weder das zweite Ergebnis beantwortet meine Frage, nicht weil es den Raum einschränkt, sondern weil es nur für SAT ist, siehe meine Antwort an Sasho Nikolov unter der Frage. Und es gibt NP-vollständige Probleme, die nicht deterministisch Ω ( n 2 ) durch Auffüllen gelöst werden können. Ich suche nach natürlichen Beispielen. nkΩ(n2)Ω(n2)
Anonym
@Anonymous Wollen Sie damit sagen, dass SAT kein natürliches Problem ist?
Sasho Nikolov
@SashoNikolov, SAT ist ein natürliches Problem. Das Ergebnis beantwortet meine Frage jedoch nicht positiv. Deshalb habe ich es so interpretiert, dass keine bessere Antwort auf meine Frage bekannt ist. Das muss nicht so sein. In diesem Sinne beantwortet es meine Frage nicht.
Anonym
2
Ich werde es ein letztes Mal versuchen: Obwohl Sie Recht haben, dass es keine derartigen Implikationen gibt, bin ich ziemlich sicher, dass es für jedes natürliche NP-Problem keine bekannte unbedingte quadratische Untergrenze gegen die deterministische Zeit gibt . Es folgt nicht aus den SAT-Ergebnissen; Es ist nur der Stand der Dinge
Sasho Nikolov
2

Ein recht naheliegendes Beispiel ist vielleicht die zeitlich begrenzte Komplexität von Kolmogorov :

kf(n)nxM|M|<f(|x|)Mx|x|k

Marzio De Biasi
quelle
Danke, es ist nicht ganz künstlich, aber ich finde es kein befriedigendes natürliches Beispiel.
Anonym
2
Ω(nk)
@SashoNikolov: Ich habe den Ramsey-Teil gelöscht ... es braucht einen formalen Beweis :-(
Marzio De Biasi
-7

Dies wirft die gleiche Frage von P = NP nur auf andere Weise auf. Wenn Sie beweisen können, dass es in quadratischer Zeit unlösbar ist oder eine absolute Untergrenze findet, beweisen Sie P! = NP

Alex Gonopolskiy
quelle
11
Warum zeigt eine quadratische Untergrenze für ein natürliches Problem in NP P! = NP?
Robin Kothari