Gibt es "O (1) -vollständige" Probleme?

Viele Komplexitätsklassen haben "vollständige" Probleme. Gibt es vollständige Probleme für die Komplexitätsklasse von Problemen, die in -Zeit gelöst werden können ? $O(1)$

Eine Komplikation ist, dass diese Klasse vom Rechenmodell abhängt; Ein Problem kann in -Zeit in einem vernünftigen Berechnungsmodell lösbar sein, in einem anderen jedoch nicht, da "vernünftig" typischerweise eine Polynomzeitäquivalenz mit einer Turing-Maschine bedeutet. Es könnte jedoch noch für bestimmte vernünftige Modelle ausgearbeitet werden. $O(1)$

Ich denke, es ist am sinnvollsten, zeitlich konstante Mehrfachreduzierungen zu betrachten. Ich bin jedoch auch offen für andere sinnvolle Reduzierungen, wenn Literatur darüber vorhanden ist.

Gibt es so etwas für ein Rechenmodell oder wurde es untersucht?

complexity-theory time-complexity constant-time Mike Battaglia
quelle

Antworten:

$\Omega(n)$ $n$

$O(n)$ $O(n^2)$

Mohemnist
quelle

Ω (n)

$\Omega(n)$

O (1)

$O(1)$

Dies setzt auch voraus, dass die Eingabe nacheinander gelesen werden muss und keine Indirektion vorliegt. Dies ist also einer der Fälle, in denen das Modell wirklich eine Rolle spielt. (Ich frage mich, ob ich in meinem ursprünglichen Beitrag auf Indirektion und möglicherweise Zufälligkeit bestehen sollte, da Sie sonst auf eine Reihe trivialer Straßensperren wie diese stoßen)

Mike Battaglia

O (1)

$O(1)$

Was meinen Sie genau mit "begrenzten konstanten Versionen anderer Probleme"?

Mike Battaglia

@MikeBattaglia zum Beispiel, wenn die Turing-Maschine nach 100 Schritten anhält.

Rus9384

$O(1)$ $L = \Sigma^*$ $L = \emptyset$

$L, L' \in O(1)$ $L \neq 0, L \neq \Sigma^*$

$x_Y \in L, x_N \notin L$

$L'$ $L$

$x$ $L'$ $O(1)$
$x \in L'$ $x_Y$ $x_N$

$L$ $O(1)$

Vor
quelle

C

$C$

C

$C$

O (1)

$O(1)$

@ Pontus: Ich stimme zu; und definitiv nicht so interessant ... es sei denn, wir leben in einem diskreten und endlichen Universum :-D

Vor

k

$k$

k

$k$

n

$n$

n / 2

$n / 2$

Ja, vielleicht kann (oder wurde) etwas Interessantes erfunden werden. Was ist das TM in Ihrem letzten Vorschlag?

Pontus

@Vor Was ist mit der festen Zeitkonstantenbreite in einem parallelen Modell?

14m2