Folge von Problemen, die zur Erhöhung von ?

7

Kennen wir eine unendliche Folge von Entscheidungsproblemen, bei denen der effizienteste Algorithmus für jedes Problem Zeit benötigt, wobei unbegrenzt zunimmt?Θ(nk)k

Nehmen wir zum Beispiel an, wir würden wissen, dass das Finden einer k-Clique , dann könnte diese Sequenz {1-Clique, 2-Clique, 3-Clique, ...} sein. Möglicherweise gibt es jedoch effizientere Algorithmen für die k-Clique, sodass diese Antwort falsch ist.Θ(nk)

BEARBEITEN:

  • Nach dem Zeithierarchiesatz (der enthält, dass "P für kein festes zu DTIME ( ) kollabiert ") sollte eine solche Sequenz existieren.nkk
  • Nach einigen Diskussionen in den Kommentaren sind häufige NP-Probleme keine guten Kandidaten. Wenn es nur Zeit braucht , um ein Zertifikat zu überprüfen (oder , wobei eine von unabhängige Konstante ist ), würde dies bedeuten, dassO(n)O(nc)ckPNP
Albert Hendriks
quelle
Für das, was es wert ist, gibt es effizientere Algorithmen für 3-Clique. Das Quadrieren der Adjazenzmatrix nimmt die Zeitreihenfolge n-zu-dem-Zwei-Punkt-Etwas und sagt Ihnen, ob es einen Zweipfad zwischen einem gegebenen Paar von Eckpunkten gibt. Jetzt überprüfen Sie einfach, ob zwischen benachbarten Scheitelpunktpaaren auch zwei Pfade liegen.
David Richerby
Schnelle Matrixmultiplikation verbessert den Exponenten in Ihren naiven Algorithmen. Zum Beispiel -cliques kann in der Zeit gefunden wird . 3kO(nωk)
Yuval Filmus
Bessere Kandidaten sind die SUM-Probleme, deren Komplexität vermutlich ungefähr . Es wurde vermutet, dass dies die genaue Komplexität ist, aber jetzt wissen wir, dass Sie subpolynomielle Faktoren gewinnen können. knk/2
Yuval Filmus
2
@j_random_hacker Wir messen die Komplexität für festes und erhöhen . kn
Yuval Filmus
1
Ist der Zeithierarchiesatz besonders nicht konstruktiv, so dass es unmöglich ist, eine solche Sequenz aus dem Beweis zu extrahieren? (Natürlich wäre dies wahrscheinlich eine sehr unnatürliche Folge von Problemen, aber wenn das nicht das ist, was Sie wollen, dann sollte das vielleicht angegeben werden)
Diskrete Eidechse

Antworten:

3

Sie lassen das Rechenmodell offen. Ich gehe davon aus, dass sich die Frage auf Direktzugriffsmaschinen (RAMs) bezieht, wie es üblich ist, wenn man nach dem tatsächlichen Exponenten in Polynomzeit fragt.

Sei die Menge von (Codierungen von) RAMs , so dass in höchstens Schritten anhält, wobei höchstens die anfänglichen Speicherzellen verwendet werden. Ein universeller RAM kann in lösen .PkMM|M|k|M|kPkO(nk)

Andererseits ist das universelle Problem für (im RAM-Modell und unter linearen Zeitreduzierungen). Als Sonderfall der RAM-Version des Zeithierarchiesatzes zeigt eine einfache Diagonalisierung, dass alle Algorithmen für die Laufzeit . So ist die Komplexität der ist als gefragt.PkDTIME(nk)PkΩ(nk)PkΘ(nk)

Die Dichtheit hängt stark vom Rechenmodell ab. Die Turing-Maschinenversion des Zeithierarchiesatzes weist eine Lücke auf. Sei die Menge von (Codierungen von) Turing-Maschinen , so dass höchstens in Schritten anhält . Dann kann in Zeit von einer universellen Turingmaschine gelöst werden und alle Algorithmen haben die Laufzeit . Ich vermute, das ist das Beste, was man tun kann.lognPkMM|M|klognPknkΩ(nklogn)

[BEARBEITEN]

In einem Kommentar fragen Sie nach konventionelleren Problemen wie Grafikproblemen oder Logik.

Lassen Sie mich zunächst darauf hinweisen, dass Clique (wie in der Antwort vorgeschlagen) kein guter Kandidat zu sein scheint. Wenn wir beweisen könnten, dass Clique Zeit (oder für ein unbegrenztes ) benötigt, haben wir impliziert, dass Clique nicht in P ist. Und damit das P unterscheidet sich von NP. Das dürfte nicht einfach sein. Das Gleiche gilt für Teile anderer Probleme, von denen wir wissen, dass sie in NP oder in anderen Klassen wie PSPACE vorliegen, von denen nicht bekannt ist, dass sie sich von P unterscheiden.kkΩ(nk)Ω(nf(k))f

Jedes Problem kann als Diagrammproblem umformuliert werden, indem die Eingabe als Diagramm codiert wird. Ich weiß nicht, ob Sie eine Graph-Version von konventionell bezeichnen würden. Ich würde es nicht natürlich nennen.Pk

Was die Logik betrifft, kann ich ein Beispiel geben. Es ist jedoch keine boolesche Logik, und es gibt eine Lücke zwischen der unteren und der oberen Grenze. Das Beispiel basiert auf dem Immerman-Vardi-Theorem. Sei eine Logik erster Ordnung, die durch Operatoren mit kleinsten Festpunkten erweitert wird. Lassen bezeichnen das Fragment , in dem nur erster Ordnung Variablen erlaubt sind. Es ist zulässig, Variablen wiederzuverwenden, daher besteht die Einschränkung darin, dass jede Unterformel höchstens freie Variablen enthält. Das Problem ist das Problem der Modellprüfung für , bei Eingabe einer Formel und einer StrukturLLkkkMkLkφLkABei übereinstimmendem Vokabular besteht die Aufgabe darin, zu entscheiden, ob , ob in wahr ist .AφφA

Mk kann in der Zeit gelöst werden . Auf der anderen Seite, für eine Konstante , ist schwer für (wo wir auch ein benötigen auf den Inhalt von Speicherzellen , gebunden ist ). Ich glaube, reicht aus. Aus der Diagonalisierung erhalten wir, dass Zeit , also benötigt Zeit . Die Grenze ist für einige nicht eng im Sinne von , aber zumindest haben wir .O(n2k+1)cM3k+cDTIME(nk)nkc=2M3k+cΩ(nk)MkΩ(nkc3)Θ(nk)knΘ(k)

Knie
quelle
Ich interessiere mich hauptsächlich für jeden Algorithmus (im Gegensatz zu bekannten ). Ich würde mich jedoch über eine Untergrenze freuen, die mit zunehmendem unbegrenzt zunimmt (im Gegensatz zu ). Wenn ich dich richtig verstehe, ist das der Fall. Es wäre großartig, eine "konventionellere" Problemsequenz zu haben (z. B. mit Graphen oder boolescher Logik). kΘ
Albert Hendriks
1
Scheint eine gute Antwort zu sein (danke!), Die durch Hinzufügen einiger Referenzen großartig gemacht werden könnte!
Raphael