Nichttriviale Probleme, die in konstanter Zeit lösbar sind?

Konstante Zeit ist die absolut niedrige Komplexität der Endzeit. Man mag sich fragen: Gibt es etwas Nichttriviales, das in konstanter Zeit berechnet werden kann? Wenn wir uns an das Modell der Turingmaschine halten, kann nicht viel getan werden, da die Antwort nur von einem Anfangssegment konstanter Länge der Eingabe abhängen kann, da weitere Teile der Eingabe nicht einmal in konstanter Zeit erreicht werden können.

Wenn wir andererseits das etwas leistungsfähigere (und realistischere) Stückkosten-RAM-Modell anwenden , bei dem Elementaroperationen mit $O(\log n)$ -Bit-Zahlen als Einzelschritte gezählt werden, können wir möglicherweise nicht-triviale Probleme lösen Aufgaben, auch in konstanter Zeit. Hier ist ein Beispiel:

Instanz: Ganzzahlen , jeweils im Binärformat durch Bits gegeben. $n, k, l, d$ $O(\log n)$

Frage: Gibt es einen Vertex-Graphen mit einer Vertex-Konnektivität von , einer Kanten-Konnektivität von und einem minimalen Grad von ? $n$ $k$ $l$ $d$

Beachten Sie, dass aus der Definition nicht einmal ersichtlich ist, dass das Problem in NP liegt . Der Grund dafür ist, dass der natürliche Zeuge (der Graph) möglicherweise eine lange Beschreibung von -Bit benötigt, während die Eingabe nur aus -Bits besteht. Andererseits hilft der folgende Satz (siehe Extremal Graph Theory von B. Bollobas). $\Omega(n^2)$ $O(\log n)$

Satz: Sei ganze Zahlen. Es existiert ein Vertex-Graph mit Vertex-Konnektivität , Kanten-Konnektivität und minimalem Grad , wenn und nur wenn eine der folgenden Bedingungen erfüllt ist: $n, k, l, d$ $n$ $k$ $l$ $d$

, $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$
$1\leq 2d+2-n\leq k\leq l = d< n-1$
$k=l=d=n-1.$

Da diese Bedingungen in konstanter Zeit überprüft werden können (im Stückkosten-RAM-Modell), führt der Satz in diesem Modell zu einem Algorithmus mit konstanter Zeit.

Frage: Was sind andere nicht triviale Beispiele für Algorithmen mit konstanter Zeit?

cc.complexity-theory ds.algorithms time-complexity Andras Farago
quelle

Zählt die Überprüfung eines probabilistisch überprüfbaren Beweises?

David Eppstein

Denken Sie nicht, dass Ihr Beispiel

-Zeit ist. Ihre Eingabe hat die Länge

, in welchem Fall das typische Wort RAM nur

-Bit-Operationen in einem Schritt zulässt. (Die Alternative besteht darin, eine der Eingabelänge proportionale Wortgröße zuzulassen, aber in diesem Fall kann man viele "Konstantzeit" -Algorithmen benennen ...) Sie könnten versuchen, eine Zeichenfolge mit einer Länge

nach diesen Zahlen hinzuzufügen , aber dann I sehe nicht, wie die Überprüfung dieses Formats in

ablaufen würde

O (1)

$O(1)$

m = O (\log n)

$m=O(\log n)$

O (\log m)

$O(\log m)$

\geq n

$\geq n$

O (1)

$O(1)$ time: muss anscheinend überprüft werden (z. B. durch binäre Suche), ob die Gesamtlänge der Zeichenfolge tatsächlich

, was

time erfordert .

Ω (\log n)

$\Omega(\log n)$

\log n

$\log n$

Ryan Williams

Ich denke, David Eppsteins Vorschlag deutet auf eine interessantere Richtung hin: die Betrachtung randomisierter O (1) -Zeit-Algorithmen. Zumindest in diesem Fall können Sie hoffen, dass in mindestens einem möglichen Durchlauf des Algorithmus auf jedes Eingabebit zugegriffen wird.

Ryan Williams

Ein einfaches Beispiel für randomisierte O (1) -Zeitalgorithmen ist der ungefähre Median (ungefähr in dem Sinne, dass die Eingabe ungefähr 50-50 aufgeteilt wird). Wählen Sie einfach 1000000 Elemente gleichmäßig zufällig aus der Eingabe aus, berechnen Sie ihren Median und geben Sie ihn aus.

Jukka Suomela

Ich mag deine Frage, aber der Nachteil deines Beispiels ist, dass es auf einem mathematischen Theorem beruht. Wenn Sie dies bis an die Grenze bringen, können Sie sagen: Instanz Positive ganze Zahlen

. Frage Gibt es eine ganze Zahl

so dass

(Antwort ist Wahr oder Falsch). Nun, es gibt tatsächlich einen konstanten Zeitalgorithmus, da die Antwort immer falsch ist, aber dies ist eindeutig nicht die Art von Beispielen, die Sie wünschen.

x, y, z

$x, y, z$

n > 2

$n > 2$

x^{n} + y^{n} = z^{n}

$x^n + y^n = z^n$

J.-E.

Antworten:

Die Arbeit Algorithmen zur Approximation konstanter Zeit mittels lokaler Verbesserungen von Nguyen und Onak enthält viele Beispiele für zufällige Näherungsverfahren konstanter Zeit: Maximum Matching (die Laufzeit hängt nur vom maximalen Grad des Graphen ab), Set Cover usw. Die Autoren präsentieren eine Methode, um solche Algorithmen zu entwerfen.

Lamine
quelle

Es gibt viele Beispiele für Spiele, die in der kombinatorischen Spieltheorie untersucht wurden, bei denen der Zustand eines Spiels durch eine konstante Anzahl von ganzzahligen Werten beschrieben werden kann. Für einige davon kann eine Gewinnstrategie für das Spiel in konstanter Zeit berechnet werden. Sie werfen aber auch Fragen auf, was genau Ihr Rechenmodell ist.

Eines der einfachsten und grundlegendsten kombinatorischen Spiele ist Nim: Man hat eine konstante Anzahl von Bohnenstapeln, und in einem Zug können Sie eine beliebige Anzahl von Bohnen von einem Stapel entfernen, entweder gewinnen oder verlieren (abhängig von Ihrer Wahl der Regeln). wenn Sie die letzte Bohne nehmen. Die optimale Strategie kann in konstanter Zeit berechnet werden, wenn Sie bitweise boolesche xor-Operationen zulassen (dh den Operator ^ in Programmiersprachen wie C / C ++ / Java / etc.). Ist dies ein Algorithmus mit konstanter Zeit in Ihrem Modell?

Hier ist einer, bei dem bekannt ist, dass es einen zeitlich konstanten deterministischen Algorithmus gibt (in einem möglicherweise unrealistischen erweiterten Berechnungsmodell, mit dem Sie die Primalität einer Zahl in konstanter Zeit testen können) bewege dich im Spiel mit Sylver-Münzen , um festzustellen, ob es sich um einen Gewinn- oder einen Verlustzug handelt. Ein Flussdiagramm für dieses Problem finden Sie in Berlecamp, Conway und Guy, Winning Ways . Es hängt jedoch von einer endlichen Menge von Gegenbeispielen für eine allgemeine Charakterisierung der Gewinnzüge ab, und es ist nicht bekannt, um welche Menge es sich handelt (oder ob es sich überhaupt handelt) leeren).

Ein weiteres interessantes Beispiel aus der kombinatorischen Spieltheorie ist Wythoffs Spiel. Jede Spielposition kann durch ein Paar von Ganzzahlen beschrieben werden (dh konstanter Raum in Ihrem Rechenmodell). Bei Bewegungen im Spiel wird eine dieser beiden Ganzzahlen auf einen kleineren Wert reduziert, und bei der Gewinnstrategie wird zu einer Position gewechselt, an der Das Verhältnis zwischen diesen beiden ganzen Zahlen liegt so nahe wie möglich am goldenen Schnitt. In vielen Spielpositionen haben Sie jedoch die Wahl: Sie können die größere der beiden Ganzzahlen entweder bis zu dem Punkt reduzieren, an dem sie (fast) die kleinere Ganzzahl multipliziert mit dem Goldenen Schnitt oder die kleinere Ganzzahl dividiert durch den Goldenen Schnitt ist. Nur eine dieser beiden Entscheidungen wird ein Gewinn sein. Die optimale Strategie kann also anhand einer konstanten Anzahl von arithmetischen Operationen definiert werden, wobei diese Operationen jedoch eine irrationale Zahl, den Goldenen Schnitt, beinhalten. Ist das ein konstanter Zeitalgorithmus in Ihrem Modell? Vielleicht ist es (eine Annäherung an das goldene Verhältnis genau Bits)nicht aber konstante Zeit unter Verwendungnur arithmetische Operationen (keine Quadratwurzeln) und ganzzahlige Konstanten Werte festgelegt? $n$ $\log n$

David Eppstein
quelle

Danke, das sind alles interessante Beispiele. Sie werfen auch ein gutes Licht auf die Tatsache, dass das Konzept der "konstanten Zeit" weniger klar ist, als ich ursprünglich dachte ...

Andras Farago

$|G|$ $G$ $p$ $m$ $m$ $|G|$ $G$ $p$ $m$ $G$ $|G|$ $m$ $m$ $m$

orgesleka
quelle