Warum die Komplexitätstheorie studieren?

Question

Ich bin ein Amateur in der Studie von Algorithmen. Für eine Weile hatte ich eine brennende Frage, Warum wir in der Informatikkomplexitätstheorie studieren? Der Grund, warum ich frage, ist, dass Algorithmen mit besser asymptotischer Komplexität für praktische Zwecke nicht immer schneller sind, tatsächlich können sie absurd langsamer sein. Warum nicht stattdessen eine Theorie entwickeln, die besser zu den praktischen Bedürfnissen der wissenschaftlichen Forschung und der Industrie passt?

Als Beispiel ist es bekannt, dass die Entwicklung eines Algorithmus zum Bestimmen eines perfekten Schachspiels in $ O (1) $ , als Anzahl der legalen Schachspiele auf einem 8 × 8-Gitter ist von oben begrenzt. Ich habe jedoch gehört, dass dieser Algorithmus länger dauert als das Alter des Universums, um zu kündigen. Dies bittet die Frage, warum die Komplexitätstheorie? Es scheint mir, dass das Feld grundsätzlich fehlerhaft ist, und Informatiker sollten einen besseren Ansatz für das Studium von Algorithmen verwenden.

(Hinweis: Mein aufrichtiger Entschuldigung an Forscher auf dem Feld. ☻)

Answer 1

Dies ist keine einfache Frage, und Sie sollten keine einfache Antwort erwarten. In diesem Raum gibt es eine Reihe ähnlicher Fragen: Warum studieren wir asymptotische Laufzeit? Warum verwenden wir asymptotische Laufzeitanalysen, um Algorithmen zu analysieren? Warum studieren wir die Komplexitätstheorie? Jeder derjenigen hat mehrere Antworten; Es gibt nicht nur einen einzigen Grund, warum wir es tun, und verschiedene Personen können unterschiedliche Gründe haben.

asymptotische Laufzeitanalyse hat Vor- und Nachteile. Sie haben eine der Nachteile genau identifiziert: Eine gute asymptotische Laufzeit garantiert in der Praxis keine gute Laufzeit. Wenn Sie sich jedoch nur auf einen einzigen Vorteil oder Nachteil konzentrieren, werden Sie nicht das vollständige Bild der Stärken und Schwächen dieses Analyses-Stils erhalten. Einige der Vorteile sind, dass die Analyse relativ fachfähig ist, sie ist nicht spezifisch für eine bestimmte Architektur, sondern bietet nützliche Informationen zur Skalierbarkeit, und zumindest teilweise ist es eine nützliche Prädiktionsleistung bei der Erkennung von algorithmischen Engpässen. Zum Beispiel der Unterschied zwischen einem A $ O (N ^ 2) $ Zeitalgorithmus und A $ o (n \ log n ) $ Zeitalgorithmus kann oft erheblich sein, auch wenn wir die konstanten Faktoren ignorieren. Einige der Nachteile sind, dass konstante Faktoren wichtig sein können, Cache- und Memory-Hierarchie-Effekte können sehr wichtig sein, werden jedoch durch asymptotische Laufzeitanalyse ignoriert, und (wie jede Metrik), die nur für asymptotische Laufzeitoptimierung optimiert werden kann, kann dies zu absurden Ergebnissen von wenig praktisch führen Dienstprogramm (siehe galaktische Algorithmen und Goodharts Gesetz ).

Ich denke, es ist auch nützlich, um die Alternative zu untersuchen. Ich ermutige Sie, die Alternative zur asymptotischen Laufzeitanalyse zu erkunden und durch das, was Sie in seiner Stelle vorschlagen würden, zu erkunden. Wenn Sie nicht versuchen, mit einem konkreten Vorschlag zu kommen, ist es leicht anzunehmen, dass es nicht so schwer sein kann, etwas besseres zu finden ... Aber wenn Sie gezwungen sind, sich auf etwas Besonderes zu verpflichten, können Sie möglicherweise herausfinden, dass es sich entdeckt anspruchsvoller als Sie erwartet haben. Zum Beispiel ermutige ich Sie, sich mit Knuths Analyse der Algorithmus-Laufzeit auf mischen in seinem Taocp-Serie. Dort tut er eine konkrete Laufzeitanalyse, ohne Asymptotika, unter Berücksichtigung der ständigen Faktoren. Wenn Sie sich zwingen, die Details davon zu arbeiten, entdecken Sie schnell die Nachteile davon: Es ist super langweilig, sehr spezifisch für eine bestimmte Computerarchitektur, und oft nicht viel mehr erleuchtender.

Wir könnten in ähnlicher Weise jedes der anderen Themen diskutieren - z. B. deshalb, warum oder warum nicht, um die Komplexitätstheorie zu studieren - und Sie sollten feststellen, dass sie auch Nuancen haben.

Ich möchte auch hervorheben, dass die Theorie- und Algorithmen-Community ein breiter ist, mit einer Reihe verschiedener Arbeitsstile. Sie scheinen alles in einen Stapel zusammenzublättern, aber es gibt ein Spektrum der Arbeit: Einige davon sind super-theoretisch und weit weg von der Praxis, einige davon ist sehr praktisch und mit konkreten Problemen motiviert und können sofort beeinflusst werden Es gibt eine Reihe von Arbeit an verschiedenen Punkten zwischen diesen Extremen. Ich denke, es ist wichtig zu verstehen, dass in der Theoriegemeinde in der Theorie-Gemeinschaft von großer praktischer Relevanz besteht oder große Auswirkungen hatte, ebenso wie Arbeiter, soweit es wesentlich theoretisch ist und nicht durch nahezudrehnte Auswirkungen motiviert ist.

Da Sie nach theoretischen Rahmenbedingungen gefragt haben, die sich auf die Bedürfnisse der Sitzung der Industrie konzentrieren, könnten Sie auch an der interessiert sein Word RAM Modell, Cache-of-Orient-Algorithmen und das parallel externer Speicher Modell.

Ich ermutige Sie dringend, die folgenden Ressourcen zu lesen, da sie eng mit Ihrer Frage verbunden sind: , warum die Polynomzeit genannt wird " Effizient "? , die Relevanz der asymptotischen Komplexität von Algorithmen zur Praxis des Entwurfs von Algorithmen , Begründung für die Vernachlässigung konstanter Faktoren in großem o .