Gemeinsame falsche Überzeugungen in der theoretischen Informatik

BEARBEITEN AM 12.10.08:

Ich werde versuchen, die Frage so zu ändern, dass möglicherweise mehr Menschen daran interessiert sind, ihre Meinung mitzuteilen. Wir brauchen Ihre Beiträge!

Dieser Beitrag ist inspiriert von dem Beitrag in MO: Beispiele für verbreitete falsche Vorstellungen in der Mathematik . Große Listen generieren manchmal eine enorme Anzahl von Antworten, deren Qualität schwer zu kontrollieren ist, aber nach dem Erfolg des entsprechenden Postings auf MO bin ich davon überzeugt, dass es hilfreich wäre, eine Reihe allgemeiner falscher Überzeugungen in Bezug auf TCS aufzulisten.

Da die Site für die Beantwortung von Fragen auf Forschungsebene vorgesehen ist, sollten Beispiele wie für nichtpolynomielle Zeit nicht auf der Liste stehen. In der Zwischenzeit wollen wir einige Beispiele, die vielleicht nicht schwer sind, aber ohne über Einzelheiten nachzudenken, sieht es auch vernünftig aus. Wir möchten, dass die Beispiele lehrreich sind und in der Regel erscheinen, wenn Sie das Thema zum ersten Mal studieren.$\mathsf{NP}$

Was sind einige (nicht triviale) Beispiele für verbreitete Irrglauben in der theoretischen Informatik, die Menschen vorkommen, die in diesem Bereich studieren?

Um genau zu sein, wollen wir Beispiele, die sich von überraschenden Ergebnissen und kontraproduktiven Ergebnissen bei TCS unterscheiden. Diese Art von Ergebnissen macht es Leuten schwer zu glauben, aber sie sind WAHR. Hier fragen wir nach überraschenden Beispielen, die die Leute auf den ersten Blick für wahr halten, aber nach einem tieferen Gedanken wird der Fehler im Inneren aufgedeckt.

Als Beispiel für die richtigen Antworten auf der Liste stammt diese aus dem Bereich der Algorithmen und der Graphentheorie:

Für einen Knoten-Graphen ist ein Kanten-Separator eine Teilmenge von Kanten der Größe , wobei die Knoten von in zwei nicht benachbarte Teile unterteilt werden können, die jeweils aus höchstens Knoten bestehen . Wir haben das folgende "Lemma":G k S k G ≤ S 3 n /$n$$G$$k$$S$$k$$G \setminus S$$3n/4$

Ein Baum hat einen 1-Kantentrenner.

Richtig?

Dies ist eines, das in der Berechnungsgeometrie häufig vorkommt, aber an anderer Stelle endemisch ist: Algorithmen für das reale RAM können ohne Effizienzverlust auf das ganzzahlige RAM (für ganzzahlige Einschränkungen des Problems) übertragen werden. Ein kanonisches Beispiel ist die Behauptung, dass die Gaußsche Eliminierung in -Zeit abläuft . In der Tat können nachlässige Eliminierungsbefehle ganze Zahlen mit exponentiell vielen Bits erzeugen .$O(n^3)$

Noch schlimmer, aber leider immer noch üblich: Algorithmen für das reale RAM mit Floor-Funktion können ohne Effizienzverlust auf das Integer-RAM übertragen werden. Tatsächlich kann ein Real-RAM + -Boden jedes Problem in PSPACE oder in #P in einer polynomiellen Anzahl von Schritten lösen .

Ich habe gerade einen weiteren Mythos geknackt, der durch die Antwort von @ XXYYXX auf diesen Beitrag beigesteuert wird :

• Ein Problem X ist -hart, wenn es eine Reduzierung der Polynomzeit (oder des Lograums) von allen -Problemen auf X gibt.N $\mathsf{NP}$$\mathsf{NP}$
• Angenommen, die Exponentialzeithypothese, 3-SAT hat keinen subexponentiellen Zeitalgorithmus. Außerdem befindet sich 3-SAT in .$\mathsf{NP}$
• Also haben keine -harten Probleme X Zeitalgorithmen. Ansonsten ein subexponentieller Zeitalgorithmus für X + eine Polynomzeitreduktion = ein subexponentieller Zeitalgorithmus für 3-SAT.$\mathsf{NP}$

Aber wir haben Unter exponentiellen Algorithmen für einige NP-schwere Probleme.

Ein falscher Glaube, der in diesem Jahr populär gemacht wurde und oft gesagt wird, wenn versucht wird, das gesamte Problem zu erklären , da als effizient erklärt wird:$P \neq NP$$P$

"Wenn , können wir eine Vielzahl von Problemen effizient lösen. Wenn nicht, können wir nicht"$P=NP$

Wenn kann gelöst werden , in O ( n g o o g o l p l e x ) , dann P = N P . Ich glaube nicht, dass irgendjemand daran denken würde, diesen Algorithmus auszuführen.$3SAT$$O(n^{googolplex})$$P=NP$

Wenn , können wir immer noch einen Algorithmus für T S P haben , der in n log ( log n ) läuft , der für n ≤ 2 32 kleiner als n 5 ist . Die meisten Menschen wären mehr als glücklich, T S P für 4 Milliarden Städte so schnell lösen zu können .$P \neq NP$$TSP$$n^{\log(\log n)}$$n^{5}$$n\leq2^{32}$$TSP$

Dies ist wirklich ein falscher Glaube an Mathematik, kommt aber häufig in TCS-Kontexten vor: Wenn die Zufallsvariablen und Y unabhängig sind, bleiben sie abhängig von Z unabhängig. (false, auch wenn Z unabhängig von X und Y ist .)$X$$Y$$Z$$Z$$X$$Y$

Distributed Computing = verteiltes Hochleistungsrechnen (Cluster, Grids, Clouds, seti @ home, ...).

Verteilte Algorithmen = Algorithmen für diese Systeme.

Spoiler: Wenn dies nicht so sehr nach einer "falschen Überzeugung" klingt, schlage ich vor, dass Sie sich Konferenzen wie PODC und DISC ansehen und herausfinden, welche Art von Arbeit die Menschen tatsächlich leisten, wenn sie sich mit theoretischen Aspekten des verteilten Rechnens befassen.

Eine typische Problemeinstellung ist die folgende: Wir haben einen Zyklus mit Knoten; die Knoten sind mit eindeutigen Kennungen aus dem Satz markierten { 1 , 2 , . . . , Poly ( n ) } ; Die Knoten sind deterministisch und tauschen Nachrichten synchron miteinander aus. Wie viele synchrone Kommunikationsrunden (als Funktion von n ) werden benötigt, um eine maximale unabhängige Menge zu finden? Wie viele Runden sind erforderlich, um eine unabhängige Menge mit mindestens n / 1000 Knoten zu finden? [Die Antwort auf beide Fragen lautet genau Θ ( log $n$$\{1,2,...,\text{poly}(n)\}$$n$$n/1000$ , 1986–2008 entdeckt.]$\Theta(\log^* n)$

Das heißt, Menschen untersuchen häufig Probleme, die aus der Sicht zentralisierter Algorithmen völlig trivial sind und mit jeder Art von Supercomputing oder Hochleistungsrechnen nur sehr wenig zu tun haben. Es geht sicherlich nicht darum, die zentralisierte Berechnung durch die Verwendung von mehr Prozessoren oder Ähnlichem zu beschleunigen.

Das Ziel besteht darin, eine Komplexitätstheorie zu erstellen, indem grundlegende Graphprobleme nach ihrer rechnerischen Komplexität klassifiziert werden (z. B. wie viele synchrone Runden benötigt werden, wie viele Bits übertragen werden). Probleme wie unabhängige Mengen in Zyklen mögen sinnlos erscheinen, aber sie spielen eine ähnliche Rolle wie 3-SAT in der zentralen Datenverarbeitung: ein sehr nützlicher Ausgangspunkt für Reduktionen. Für konkrete reale Anwendungen ist es sinnvoller, Geräte wie Router und Switches in Kommunikationsnetzwerken anstelle von Computern in Grids und Clustern zu betrachten.

Dieser falsche Glaube ist nicht ganz harmlos. Tatsächlich ist es ziemlich schwierig, theoretische Arbeiten zu verteilten Algorithmen an das allgemeine TCS-Publikum zu verkaufen. Ich habe lustige Schiedsrichterberichte von TCS-Konferenzen erhalten ...

$T(n) = 2T(n/2) + O(n \log n)$$T(1) = 1$

$n=1$$n$

$\begin{align} T(n) &= 2 \cdot T(n/2) + O(n \log n) \\ &= 2 \cdot O(n/2 \log n/2) + O(n \log n) \\ &= O(n \log n/2) + O(n \log n) \\ &= O(n \log n) \\ \end{align}$

QED (ist es?)

$M$$T(n)$$M_o$$O(T(n)\log T(n))$

• $M_o$
• $M_o$$\Theta(T(n)\log T(n))$

(Siehe diesen Beitrag von rjlipton zum Beispiel)

$EXP-TIME\neq NEXP-TIME$$\Theta(T(n)\log T(n))$$M_o$$M_o$$O(T(n)\log T(n))$$T:\mathbb{N}\rightarrow\mathbb{N}$$\Theta(T(n)\log T(n))$$O(T(n)\log T(n))$$EXP-TIME=NEXP-TIME$

Der Beweis dieser Behauptung ist dem Beweis in der Antwort von Q1 hier sehr ähnlich , deshalb werden wir nur die Schlüsselideen geben.

$L\in NEXP-TIME$$L\subseteq\{0,1\}^*$$k\in\mathbb{N}$$L$$M$$2^{n^k}$$M$

$g(n)=\Theta(f(n)\log f(n))$$g$

$L$

• $x$$n$$x00\ldots 0$$|x|^{k-1}$$x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$
• $g(n)$$g(n)$$g(n)$$x\in L$$x\not\in L$$n$$g$

$L$$L\in NEXP-TIME$$EXP-TIME=NEXP-TIME$

Hier sind meine zwei Cent:

$\mathsf{RL}$$\mathsf{RP}$$M$

• $M$$1/2$
• $M$$1$

Außerdem bleibt die Maschine immer stehen.

Ist die Definition korrekt? (Nein)

$f$$g$$1^n$$f(n)$$g(n)$$f(n+1)=o(g(n))$

$NTIME(f(n))\subsetneq NTIME(g(n))$

Nun, die Hierarchie gibt tatsächlich nur . Wir brauchen zB für . Für Funktionen , so dass , , ist sehr verbreitet. Genau genommen wird die nicht deterministische Zeithierarchie jedoch oft oberflächlich angegeben.$NTIME(g(n)) - NTIME(f(n))\neq\emptyset$$f(n)\leq g(n)$$NTIME(f(n))\subsetneq NTIME(g(n))$$f,g$$f(n+1)=o(g(n))$$f(n)\leq g(n)$

Um zu zeigen , dass nicht gilt für alle vollzeit konstruierbar st definieren und . Es ist leicht zu erkennen, dass und vollständig sind und . Aus der nicht deterministischen Zeithierarchie wissen wir, dass es eine Sprache über . Definiere $NTIME(f(n))\subseteq NTIME(g(n))$$f,g$$f(n+1)=o(g(n))$

Daraus folgt . Es ist leicht zu erkennen, dass aus folgt , was nicht wahr ist. Daher .$L_1\in NTIME(f(n))$$L_1\in NTIME(g(n))$$L\in NTIME((n+1)^2)$$L_1\in NTIME(f(n))-NTIME(g(n))$

Ich habe oft gehört, dass Valiant-Vazirani sagt, dass zufällig auf reduziert wird , oder dass , oder dass . Dies würde insbesondere bedeuten, dass wenn Valiant-Vazirani derandomisiert werden könnte, . Aber tatsächlich sagt Valiant-Vazirani, dass .U P N P ⊆ R P U P N P ⊆ R ⋅ U P N P = U P N P ⊆ R P P r o m i s e U $\mathsf{NP}$$\mathsf{UP}$$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{UP}}$$\mathsf{NP} \subseteq \mathsf{R} \cdot \mathsf{UP}$$\mathsf{NP}=\mathsf{UP}$$\mathsf{NP} \subseteq \mathsf{RP}^{\mathsf{PromiseUP}}$

Eng verwandter falscher Glaube: ist die Klasse der Sprachen mit einem nichtdeterministischen Polyzeitprüfer, so dass wenn es einen eindeutigen Zeugen gibt. Die Korrektur besteht darin, dass der Prüfer die semantische Eigenschaft erfüllen muss, dass es in allen Fällen höchstens einen Zeugen gibt. Die obige Definition ohne die Korrektur ist die Definition von . Aber sich stark von : Zum Beispiel . L x ∈ L U S U S U P C O N P ⊆ U $\mathsf{UP}$$L$$x \in L$$\mathsf{US}$$\mathsf{US}$$\mathsf{UP}$$\mathsf{coNP} \subseteq \mathsf{US}$

$\mu$$X$$\{X=\mu\}$