Charakterisierung von Problemen, für die sublineare Zeitalgorithmen existieren

16

Ich habe mich gefragt, ob Probleme, für die sublineare Zeitalgorithmen (in der Eingabegröße) existieren, als solche mit spezifischen Eigenschaften charakterisiert werden können. Dies umfasst die sublineare Zeit (z. B. Eigenschaftstests, ein alternativer Begriff der Approximation für Entscheidungsprobleme), den sublinearen Raum (z. B. Skizzier- / Streaming-Algorithmen, bei denen die Turing-Maschine über ein Nur-Lese-Band, einen sublinearen Arbeitsraum und eine Nur-Schreib-Ausgabe verfügt Band) und sublineare Messungen (z. B. spärliche Erholung / Druckmessung). Insbesondere interessiert mich eine solche Charakterisierung sowohl für das Framework von Eigenschaftstestalgorithmen als auch für das klassische Modell von randomisierten Algorithmen und Approximationsalgorithmen.

Beispielsweise weisen die Probleme, für die eine dynamische Programmierlösung existiert, eine optimale Unterstruktur und überlappende Unterprobleme auf; diejenigen, für die es eine gierige Lösung gibt, weisen eine optimale Unterstruktur und die Struktur einer Matroid auf. Und so weiter. Jede Referenz zu diesem Thema ist willkommen.

Mit Ausnahme einiger Probleme, die einen deterministischen sublinearen Algorithmus zulassen, sind fast alle der sublinearen Algorithmen, die ich gesehen habe, randomisiert. Gibt es eine spezielle Komplexitätsklasse für Probleme, die sublineare Zeitalgorithmen zulassen? Wenn ja, ist diese Klasse in BPP oder PCP enthalten?

Massimo Cafaro
quelle
5
sublineare Zeit in welchem ​​Modell?
Kaveh
1
Algorithmen zum Testen von Eigenschaften befinden sich im allgemeinen Rahmen Ihrer Anforderungen, aber Kavehs Punkt muss zuerst beantwortet werden.
Suresh Venkat
Ich habe meine Frage bearbeitet und die angeforderten Informationen hinzugefügt.
Massimo Cafaro
Die Fourier-Transformation eines Vektors kann in sublinearer Zeit berechnet werden, wenn sie im Frequenzbereich (fast) sparsam ist. Die Eigenschaft hier ist also Sparsamkeit. Überprüfen Sie zum Beispiel "Einfacher und praktischer Algorithmus für sparsame Fourier-Transformation" von Haitham Hassanieh, Piotr Indyk, Dina Katabi und Eric Price nms.lcs.mit.edu/~dina/pub/soda12.pdf und die darin enthaltenen Referenzen. k
Dimitris

Antworten:

13

Für die zeitlich konstante Prüfung von Grapheneigenschaften ist eine interessante Charakterisierung bekannt. Eine Grapheneigenschaft ist eine Funktion von allen Graphen zu , und eine Grapheneigenschaft ist testbar, wenn es einen randomisierten Algorithmus , der für alle und alle Graphen :{0,1}PEINε>0G

  • EIN(G) liest nur Kanten von für eine FunktionG(ε)GG
  • Wenn dann gibt mit hoher Wahrscheinlichkeit "Ja" aus (sagen wir, mindestens ).P(G)=1EIN(G)2/3
  • Wenn mindestens Kanten von hinzugefügt oder entfernt werden müssen, um ein zu erhalten so dass ( dh ist -far von der Eigenschaft ), dann gibt "nein" mit einer Wahrscheinlichkeit von mindestensεn2GGP(G)=1GεEIN(G)2/3

Das heißt, kann zwischen Graphen mit und Graphen mit hohem Bearbeitungsabstand von Graphen mit . Alon, Fischer, Newman und Shapira haben bewiesen, dass eine Eigenschaft nur dann auf diese Weise testbar ist, wenn die Eigenschaft auf die Eigenschaft "reduziert" werden kann, zu prüfen, ob ein Graph eine reguläre Partition aufweist (im Sinne von Szemeredi) ). Dies zeigt, dass das Testen der Regelmäßigkeit in gewissem Sinne "vollständig" ist. (Es gibt auch eine einseitige Fehlerversion der Testbarkeit, siehe Referenz.)EINPPPε

Ryan Williams
quelle
5

Im Bereich des sublinearen Raums gibt es keine explizite Klasse von Problemen, die eine sublineare Raumlösung zulassen, aber es gibt große Klassen von Problemen (Frequenzmomentschätzung, Dimensionsreduktion usw.), bei denen das Vorhandensein einer kleinen "Skizze" gezeigt werden kann führt zu effizienten Algorithmen.

Aber auch in diesem Bereich sind alle Algorithmen randomisiert, und es gibt stark deterministische Untergrenzen, die hauptsächlich auf der Komplexität der Kommunikation beruhen.

Suresh Venkat
quelle