Kompromiss zwischen Zeit und Abfragekomplexität

Das direkte Arbeiten mit Zeitkomplexität oder Schaltkreisuntergrenzen ist beängstigend. Daher entwickeln wir Tools wie die Komplexität von Abfragen (oder die Komplexität von Entscheidungsbäumen), um die unteren Grenzen in den Griff zu bekommen. Da jede Abfrage mindestens einen Einheitsschritt dauert und Berechnungen zwischen Abfragen als frei gezählt werden, ist die Zeitkomplexität mindestens so hoch wie die Abfragekomplexität. Können wir jedoch etwas über die Trennungen sagen?

Ich bin neugierig auf die Arbeit in der klassischen Literatur oder in der Quantenliteratur, biete aber Beispiele aus dem Bereich der Qualitätskontrolle an, da ich besser vertraut bin.

Bei einigen bekannten Algorithmen wie Grovers Suche und Shors Periodensuche liegt die Zeitkomplexität innerhalb der polylogarithmischen Faktoren der Abfragekomplexität. Für andere, wie das Problem der versteckten Untergruppen, besteht eine Komplexität der Polynomabfrage, jedoch sind keine polynomiellen Zeitalgorithmen bekannt.

Da möglicherweise eine Lücke zwischen Zeit und Abfragekomplexität besteht, ist nicht klar, dass ein optimaler Zeitkomplexitätsalgorithmus dieselbe Abfragekomplexität aufweisen muss wie der optimale Abfragekomplexitätsalgorithmus.

Gibt es Beispiele für Kompromisse zwischen Zeit und Abfragekomplexität?

Gibt es Probleme, bei denen der bekannteste Algorithmus für die Zeitkomplexität eine andere Abfragekomplexität aufweist als der bekannteste Algorithmus für die Abfragekomplexität? Mit anderen Worten, können wir mehr Abfragen durchführen, um die Operationen zwischen Abfragen zu vereinfachen?

Oder gibt es ein Argument, das zeigt, dass es immer eine Version eines asymptotisch optimalen Abfragealgorithmus mit einer Implementierung mit asymptotisch bester Zeitkomplexität gibt?

Hier ist ein Versuch, eine künstliche Funktion mit der folgenden Eigenschaft zu erstellen:

• Das Problem kann mit Abfragen gelöst werden, benötigt aber exp ( n ) Zeit.$O(\log n)$$\exp(n)$
• Das Problem kann mit Zeit gelöst werden , dies erfordert jedoch O ( n ) Abfragen$O(n)$$O(n)$

Die Eingabegröße sei . Lassen Sie die ersten log n Bits (nennen wir diese Zeichenfolge x) die Eingabe für ein Problem codieren, das für EEXP abgeschlossen ist. Die nächsten n Bits (nennen wir diesen String y) haben die Eigenschaft, dass sie alle Null sind, wenn x eine NO-Instanz des EEXP-Complete-Problems ist.$n + \log n$$\log n$$n$

In Worten, die ersten n Bits codieren ein hartes Problem, und die nächsten n Bits geben Ihnen einen Hinweis auf die Lösung des Problems. Um die Lösung jedoch durch Betrachten der n- Bit-Zeichenfolge herauszufinden, führen Sie Ω ( n ) -Abfragen durch.$\log n$$n$$n$$\Omega(n)$

Dieses Problem kann also gelöst werden, indem entweder nur die ersten Bits gelesen werden und exp (n) Zeit aufgewendet wird oder indem n Bits gelesen werden und nur lineare Zeit verwendet wird.$\log n$$n$

Dieselbe Funktion wird für die Komplexität von Quantenabfragen verwendet. Fügen Sie bei Bedarf Quadratwurzelzeichen ein.

Eine extremere Version von Robins Beispiel:

Die Eingabegröße sei , wobei die ersten n - 1 Bits (nennen Sie diese Zeichenfolge x ) eine Turing-Maschine T x codieren . Fixiere eine Funktion f ( n ) . Das letzte Bit der Zeichenkette sei 1, wenn die Turingmaschine T x in weniger als f ( n ) Schritten anhält . Das Problem ist dann zu bestimmen, ob T x in weniger als f ( n ) Schritten anhält und die Parität von x gerade ist.$n$$n-1$$x$$T_x$$f(n)$$1$$T_x$$f(n)$$T_x$$f(n)$$x$

Durch Ausführen von Abfragen kann das Problem in der Zeit O ( f ( n ) ) gelöst werden , während durch Ausführen von n Abfragen das Problem in der Zeit O ( n ) gelöst werden kann .$n-1$$O(f(n))$$n$$O(n)$

Ich mag Robin Kotharis Antwort und Joe Fitzsimons 'Modifikation. In einer offensichtlichen Erweiterung ihrer Antworten können sie ein beliebiges Trennungsverhältnis (außer Konstante gegen Nichtkonstante) zwischen der kleineren und größeren Abfragekomplexität und der größeren und kleineren Zeitkomplexität erzielen. Es gibt jedoch keinen offensichtlichen Weg, ihre Funktionen nicht partiell zu machen. Ich möchte auf ein natürliches Problem hinweisen, bei dem wir eine Trennung haben und zeigen, dass große Trennungen für Gesamtfunktionen schwieriger sind.

Ein natürliches Problem

Ben Reichardt wies per E-Mail auf das Problem der Formelbewertung hin. Die Komplexität der Quantenabfrage für die Auswertung einer allgemeinen UND-ODER-Formel zum einmaligen Lesen für Variablen beträgt Θ ( $n$. DasO($\Theta(\sqrt{n})$-Anfragealgorithmus ist nicht zeiteffizient. Hierwird der schnellste bekannte Algorithmus gezeigt, umO( √ zu machen$O(\sqrt{n})$abfragen und zeitlich polylogarithmisch schlechter laufen. Somit haben wir ein natürliches Gesamtproblem, bei dem es eine bekannte Trennung gibt. Obwohl es keinen Beweis dafür gibt, dass diese Trennung existieren muss.$O(\sqrt{n}\log{n})$

Gesamtfunktionen sind schwerer zu trennen?

Mir scheint es schwerer, Gesamtfunktionen mit nachweisbaren Trennungen zu finden. Um zu zeigen, dass der Fall von Gesamt- und Teilfunktionen unterschiedlich ist, werde ich die größte Trennung zwischen den Abfragekomplexitäten des abfrageoptimalen und des zeitoptimalen Algorithmus für eine Gesamtfunktion diskutieren.

$m$$\Omega{(\log m)}$$m$$n$$n - m$$m$$0$

$(\text{query complexity}\; , \; \text{time complexity})$$(q_1(n),t_1(n))$$(q_2(n),t_2(n))$$q_2(n) \leq f(q_1(n))$$f(n) = O(2^n)$

[1] HU Simon, "Ein knappes Z (loglogn) an die Zeit gebunden, in der parallele RAMs nicht entartete Boolesche Funktionen berechnen", in: Symp. zu Grundlagen der Computertheorie, Lecture Notes in Computer Science, Bd. 158, Springer, Berlin, 1983, S. 439–444.