Ändert sich die zeitliche Komplexität eines Problems mit der Codierung des Problems?

7

Angenommen, ich habe ein Entscheidungsproblem und codiere es in eine Sprache . Jetzt kann ich es auch in eine andere Sprache kodieren . $D$ $L \subset \{0,1\}^*$ $L'$

Gibt es einen Satz über die zeitliche Komplexität von und ? $L$ $L'$

Wie ändert sich die zeitliche Komplexität eines Problems mit unterschiedlichen Codierungen desselben Problems?

complexity-theory terminology time-complexity user774025
quelle

1

Eine spärliche Sprache ist eine Sprache, in der die Anzahl der Zeichenfolgen der Länge durch eine Polynomfunktion von . Alle unären Sprachen sind spärlich. Mahaneys Theorem besagt, dass wenn eine spärliche Sprache NP-vollständig ist, P = NP ist.

n

$n$

n

$n$

Pål GD

8

Ja, die Komplexität hängt von der Codierung ab. Das einzige, dessen Sie sich sicher sein können, ist, dass wenn die Übersetzung von der Codierung in die Codierung oder umgekehrt die Komplexität hat und mit der Komplexität gelöst werden kann , (dasselbe Problem, das mit der Codierung ausgedrückt wird ) dies kann mit der Komplexität gelöst werden, indem zwischen den Codierungen hin und her gewechselt wird. $L$ $L'$ $f$ $D$ $g$ $D'$ $L'$ $O(f+g)$

Es ist nicht nur eine Frage der Länge der Codierung. Um ein einfaches Beispiel zu geben, sei eine positive ganze Zahl, die binär dargestellt wird, und eine positive ganze Zahl, die durch ihre Primfaktorisierung dargestellt wird. Es gibt ein Polynom, das in der Größe einer Darstellung in Bezug auf die andere gebunden ist. Lange Zeit war nicht bekannt, ob Primalitätstests in der binären Darstellung in Polynomzeit gelöst werden können; In der Faktorisierungsdarstellung ist es jedoch trivial polynomisch (wahrscheinlich abhängig von den Darstellungsdetails). $L$ $L'$ $O(1)$

Oder betrachten Sie das Entscheidungsproblem als „Ganzzahl“ $n$ ein Mitglied von Set $S$ ”. Wenn die Menge durch eine ungeordnete Liste von ganzen Zahlen dargestellt wird, erfordert dieses Problem offensichtlich mindestens eine lineare Zeit. Wenn die Menge jedoch durch einen ausgeglichenen Suchbaum dargestellt wird, ist die Suchzeit in der Größe der Menge polylogarithmisch.

In den meisten konkreten Fällen gibt es eine offensichtliche Darstellung, die jeder annimmt, oder genauer gesagt, es gibt eine Klasse von Darstellungen, die alle einer Transformation entsprechen, die vernachlässigbare Zeit in Anspruch nimmt. Manchmal ist die Darstellung jedoch relevant, am häufigsten, wenn Datenstrukturen genauer als die Polynomzeit analysiert werden.

Gilles 'SO - hör auf böse zu sein'
quelle

Ich mag Ihren Hinweis auf Datenstrukturen. Die Laufzeit vieler Graph-Algorithmen hängt entscheidend von der gewählten Graph-Darstellung ab, die als Eingabecodierung angesehen werden kann.

Raphael

6

Die zeitliche Komplexität hängt von der Codierung ab. Die zeitliche Komplexität für $L$ und $L'$ könnte bei einer ausreichend verrückten Codierung beliebig weit voneinander entfernt sein.

In der Praxis kümmern wir uns normalerweise um die zeitliche Komplexität einer "natürlichen" Codierung. Wenn es mehrere "natürliche" Codierungen gibt, führen diese häufig zu ungefähr derselben zeitlichen Komplexität (z. B. wenn Sie effizient zwischen den Codierungen konvertieren können). Es gibt jedoch keine formelle Garantie dafür.

Technisch gesehen kann man daher nicht von der zeitlichen Komplexität eines Problems sprechen, ohne die bestimmte verwendete Codierung anzugeben.

DW
quelle

Gibt es eine strenge Definition von "natürlicher Kodierung"?

user774025

1

@ user774025, nein. Beispiel: Eine natürliche Codierung einer Ganzzahl

x

$x$ ist die Ganzzahl in binärer Form aufzulisten. Eine natürliche Kodierung einer Liste

L = [x_{1}, x_{2}, \dots, x_{n}]

$L=[x_1,x_2,\dots,x_n]$ ist die Verkettung der Kodierung von

x_{1}

$x_1$ , die Kodierung von

x_{2}

$x_2$ usw. (mit geeigneten Trennzeichen). Und so weiter.

DW

@ user774025 Mit anderen Worten, nein, gibt es nicht.

Patrick87

5

Betrachten Sie jede NP-vollständige Sprache $L$ und sein Brute-Force-Löser (daher Exponentialzeitlöser) $A$ . Nun definieren

$\qquad L' = \{ x\$0^{|x|^{|x|}} \mid x \in L \}$ .

Nun klar, eine leichte Anpassung von $A$ (Verwenden Sie die Eingabe nur bis zu $\$$ ) entscheidet $L'$ in der Zeit exponentiell in $|x|$ und damit im Zeitpolynom in der Länge seiner eigenen Eingabe (die von ist $L'$ ). Das ist, $L' \in \mathsf{P}$ .

Eine einfachere Überlegung besteht darin, von der Standard-Binärcodierung zur unären Codierung überzugehen. Plötzlich laufen triviale Primalitätsprüfungen und sogar Faktorisierungen in Polynomzeit ab. Dieses Konzept bezieht sich auf die pseudo-polynomielle Laufzeit .

Also ja: Die Codierung ist wichtig, wenn sich die Eingabelänge erheblich ändert . Daher ist die typische Annahme zu verwenden

eine nicht unäre Codierung mit
höchstens ein konstanter Faktor Overhead (über die bloßen Informationen),

so vage wie das ist.

Beachten Sie, dass nicht einmal Laufzeiten in Bezug auf $\Theta$ -Klassen sind allein unter Verwendung dieser Annahme unveränderlich. Stellen Sie sich eine Codierung von Arrays vor, die die Zahlen verschachtelt. Dies fügt dem Finden des Maximums einen Polynomfaktor hinzu. Daher sollten Sie wahrscheinlich auch bei "guten" Codierungen vorsichtig sein, wenn Sie etwas mit höherer Granularität als bis zu Polynomfaktoren sagen möchten.

Raphael
quelle

4

Nicht gerade eine Antwort auf Ihre Frage, aber die Berman-Hartmanis-Vermutung besagt (informell), dass alle NP-vollständigen Probleme in gewissem Sinne Kodierungen voneinander sind. Der in der Vermutung verwendete Begriff der Codierung bewahrt die Zeitkomplexität bis zu einem Polynomunterschied.

Yuval Filmus
quelle

"Nicht gerade eine Antwort auf Ihre Frage" - ist es dann ein Kommentar? ;)

Raphael

Ändert sich die zeitliche Komplexität eines Problems mit der Codierung des Problems?

Antworten: