Sollten wir durch Reduzierungen mehr oder weniger optimistisch in Bezug auf die Tractability eines Problems sein?

Mir scheint, dass die meisten Komplexitätstheoretiker im Allgemeinen die folgende philosophische Regel glauben:

Wenn wir nicht einen effizienten Algorithmus für Problem herauszufinden , können , und wir können Problem reduzieren zu Problem , dann gibt es wahrscheinlich keinen effizienten Algorithmus für Problem , entweder.$A$$A$$B$$B$

Dies ist der Grund, warum wir zum Beispiel, wenn ein neues Problem als NP-vollständig erwiesen ist, es einfach als "zu schwer" ablegen, anstatt uns über einen neuen Ansatz (Problem ) zu freuen , der möglicherweise P = N P ergibt .$B$$P = NP$

Ich habe das mit einem Kommilitonen aus einem anderen wissenschaftlichen Bereich besprochen. Sie fand diese Idee äußerst eingängig. Ihre Analogie:

Sie sind ein Entdecker, der nach einer Brücke zwischen dem nordamerikanischen und dem asiatischen Kontinent sucht. Seit vielen Monaten haben Sie versucht und es nicht geschafft, eine Landbrücke vom amerikanischen Festland nach Asien zu finden. Dann entdecken Sie, dass das US-amerikanische Festland auf dem Landweg mit dem alaskischen Gebiet verbunden ist. Sie erkennen, dass eine Landbrücke von Alaska nach Asien eine Landbrücke vom US-amerikanischen Festland nach Asien bedeuten würde, von der Sie sich ziemlich sicher sind, dass sie nicht existiert. Sie verschwenden also keine Zeit mit Erkundungen in der Nähe von Alaska. Du gehst einfach nach Hause.

Unsere vorherige philosophische Regel klingt in diesem Zusammenhang ziemlich albern. Mir fiel keine gute Gegenargumentation ein! Also übergebe ich es euch: Warum sollten wir eine Reduktion so behandeln, dass es Problem B schwerer macht, als Problem A einfacher zu machen?$A \to B$$B$$A$

Ich denke das ist eine sehr gute Frage. Um darauf zu antworten, müssen wir erkennen, dass:

• nicht alle ermäßigungen sind gleich,
• um uns optimistisch zu fühlen, müssen wir etwas lernen, das wirklich hilfreich ist.

Wenn wir eine nichttriviale Reduktion feststellen , fällt sie normalerweise in eine der folgenden Kategorien:$A \to B$

1. Wir haben etwas Nützliches über Problem A gelernt (und nichts über Problem B).
2. Wir haben etwas Entmutigendes über Problem B gelernt (und nichts über Problem A).

Etwas genauer lassen sich diese beiden Fälle wie folgt charakterisieren:

1. Wir haben herausgefunden, dass Problem A eine versteckte Struktur hat, die es ermöglicht, einen neuen, cleveren Algorithmus zum Lösen von Problem A zu entwerfen. Wir müssen nur wissen, wie man Problem B löst.

2. Wir haben festgestellt, dass das Problem B in einigen Sonderfällen im Grunde nur das Problem A in Verkleidung ist. Wir können jetzt sehen, dass jeder Algorithmus zum Lösen von Problem B mindestens diese Sonderfälle richtig lösen muss; und das Lösen dieser Sonderfälle ist im Wesentlichen gleichbedeutend mit dem Lösen von Problem A. Wir sind wieder auf dem ersten Platz: Um bei Problem B Fortschritte zu erzielen, müssen wir zuerst bei Problem A Fortschritte erzielen.

Reduzierungen des Typs 1 sind im Kontext positiver Ergebnisse häufig, und dies sind sicherlich gute Gründe, sich optimistisch zu fühlen.

Berücksichtigt man jedoch Härteminderungen, die beispielsweise bei NP-Härteprüfungen auftreten, handelt es sich fast immer um Typ 2.

Beachten Sie, dass Sie auch dann, wenn Sie nichts über die Komplexität der Berechnung von Problem A oder Problem B wissen, feststellen können, ob Ihre Reduktion vom Typ 1 oder Typ 2 ist Bestimmen Sie, ob wir uns optimistisch oder pessimistisch fühlen sollten. Wir können nur sehen, was wir dank der Reduzierung gelernt haben.

Was in der Analogie fehlt, ist eine Vorstellung der relativen Entfernungen. Ersetzen wir Alaska in unserer Analogie mit dem Mond:

Sie sind ein Entdecker, der nach einer Brücke zwischen dem nordamerikanischen und dem asiatischen Kontinent sucht. Seit vielen Monaten haben Sie versucht und es nicht geschafft, eine Landbrücke vom amerikanischen Festland nach Asien zu finden. Dann entdecken Sie, dass das amerikanische Festland auf dem Landweg mit dem Mond verbunden ist. Sie sind bereits zuversichtlich, dass der Mond von Asien weit entfernt ist, und können sich daher darauf verlassen, dass Nordamerika durch die Dreiecksungleichheit auch von Asien weit entfernt ist.

Es ist nicht wahr, dass wir Reduktionssätze immer als Aussagen zur Härte betrachten. In Algorithmen reduzieren wir beispielsweise häufig ein Problem auf LP und SDP, um sie zu lösen. Diese werden nicht als Härteergebnisse interpretiert, sondern als algorithmische Ergebnisse. Obwohl es sich technisch gesehen um Kürzungen handelt, bezeichnen wir diese jedoch häufig nicht als solche. Was wir unter einer Reduktion verstehen, ist normalerweise eine Reduktion auf ein (NP-) schweres Problem.

$A$$B$$A$$B$$B$$A$$A$$A$$B$$B$. Die meisten Forscher finden es wahrscheinlicher, dass P nicht gleich NP ist, und nehmen sogar an, dass SAT exponentielle Zeit benötigt. Mit anderen Worten wird angenommen, dass SAT sehr schwer ist. Wenn Sie diese Vermutungen akzeptieren, ist es völlig vernünftig, Reduktionen zu betrachten, die die Universalität eines Problems für NP als das Problem beweisen, das schwierig ist. (Warum Forscher feststellen, dass P ungleich NP ist, ist ein anderes Problem. Es gab mehrere Blog-Posts in Theorie-Blogs darüber.)

Ein Grund dafür, dass wir untere Schranken durch Universalitätsergebnisse ersetzen (dh, dass jedes Problem in einer Klasse auf das Problem reduziert wird), ist, dass wir keine guten allgemeinen unteren Schranken nachweisen können (dies entspricht dem aktuellen Wissensstand) dass SAT in linearer deterministischer Zeit gelöst werden kann).

Eigentlich hätte die Entdeckung Alaskas zumindest zunächst den gegenteiligen Effekt. Da es sich so weit nach Westen erstreckt, lässt es die Leute denken, dass es vielleicht doch eine Landbrücke gibt (die Analogie lautet , hey, vielleicht P  =  NP, da dieses neue NP- vollständige Problem wie ein so guter Kandidat für aussieht) mit einer Polynom-Zeit-Lösung). Wenn Alaska jedoch einmal gründlich erkundet und keine Landbrücke gefunden worden wäre, wären die Menschen wahrscheinlich überzeugter als zuvor, dass Asien und Amerika getrennt sind.

Die Frage führt eine bestimmte Analogie / Metapher ein, die von Experten nicht häufig verwendet wird, und konzentriert sich nur auf P / NP. Andere Komplexitätsklassen werden nicht erwähnt, wohingegen Experten sie als ein großes zusammenhängendes Universum von Entitäten betrachten, wie in dem von Kuperberg erstellten bemerkenswerten Diagramm . Es wäre ordentlich, eine große Liste von Analogien von Komplexitätsklassen zusammenzustellen, es gibt viele solcher Analogien. Es geht um das "Wegfeilen" von Problemen, die sich als vollständig erwiesen haben, und um die "Aufregung über neue Ansätze".

Man kann verstehen, dass die Entdeckung der NP-Gesamtklasse anfänglich "aufgeregt" war, aber nach über vier Jahrzehnten intensiver Bemühungen, zu beweisen, dass P ≠ NP nicht vielversprechend war, ist eine gewisse "Aufregung" verflogen, und einige Forscher sind der Meinung, dass wir es nicht geschafft haben sind nicht näher. Die Geschichte ist voll von Forschern, die jahrelang an Problemen gearbeitet haben, ohne oder mit großen offensichtlichen Fortschritten, manchmal mit späterem Bedauern. NP complete kann also (um Aaronsons Analogie auszuleihen) als eine Art "elektrischer Zaun" dienen, eine Warnung / Einschränkung, sich nicht zu sehr auf Versuche einzulassen, (hier buchstäblich in mehr als einer Hinsicht) "unlösbare" Probleme zu lösen.

Es ist wahr, dass es einen Hauptaspekt der "Katalogisierung" von NP-Gesamtproblemen gibt, der immer noch andauert. Es werden jedoch weiterhin umfangreiche "feinkörnigere" Untersuchungen zu wichtigen NP-Gesamtproblemen (SAT, Cliquendetektion usw.) durchgeführt. (Tatsächlich tritt ein sehr ähnliches Phänomen bei unbestreitbaren Problemen auf: Sobald es sich als unbestreitbar erwiesen hat, ist es so, als würden sie für weitere Untersuchungen als "Niemandsland" eingestuft.)

Daher sind alle NP- Gesamtprobleme nach heutiger Theorie gleichwertig, was sich manchmal in auffälligen Vermutungen wie der Berman-Hartmanis- Isomorphismus-Vermutung zeigt. Die Forscher sind zuversichtlich, dass sich dies eines Tages ändern wird.

Diese Frage ist soft-questionmit gutem Grund gekennzeichnet. Sie werden nicht viele ernsthafte Wissenschaftler finden, die in ihren Beiträgen Analogien diskutieren, die sich in die Populärwissenschaft verwandeln , und sich stattdessen lieber auf mathematische Präzision / Genauigkeit konzentrieren (und wie in den Kommunikationsrichtlinien für diese Gruppe hervorgehoben). Dennoch gibt es hier einen gewissen Wert für die Aufklärung und Kommunikation mit Außenstehenden / Laien.

hier sind ein paar "Gegen-Analogien" für Laien zusammen mit "Forschung führt" zu den Konzepten. Dies könnte zu einer längeren Liste gemacht werden.

• Es gibt eine Analogie der Gebiete in der Frage. Es ist jedoch sinnvoller, an wichtige Bereiche der Komplexitätstheorie zu denken, einschließlich der Terra Incognita innerhalb bekannter Klassen . Mit anderen Worten, es gibt einen Bereich von P intersect NP. Sowohl P als auch NP sind ziemlich gut verstanden, aber es ist nicht bekannt, ob der Bereich P ⋂ NP-hart (P schneidet NP-hart) leer ist oder nicht.

• Aaronson gab kürzlich die Metapher von zwei anscheinend verschiedenen Arten von Fröschen, die sich für P / NP niemals mischen. er bezog sich auch auf den "unsichtbaren Elektrozaun" zwischen den beiden.

• Die Teilchenphysik untersucht das Standardmodell. Die Physik untersucht die Zusammensetzung von Partikeln ebenso wie die Komplexitätstheorie die Zusammensetzung von Komplexitätsklassen. In der Physik gibt es eine gewisse Unsicherheit darüber, wie manche Teilchen andere hervorrufen ("Grenzen setzen"), genau wie in der Komplexitätstheorie.

• " The Complexity Zoo" ist wie eine Menge exotischer Tiere mit unterschiedlichen Fähigkeiten, von denen einige klein / schwach und andere groß / mächtig sind.

• Komplexitätsklassen sind wie ein glattes Zeit / Raum-Kontinuum, wie in den Zeit / Raum- Hierarchiesätzen mit wichtigen "Übergangspunkten" (überraschenderweise ziemlich analog zu Phasenübergängen der physikalischen Materie) zwischen den verschiedenen Zuständen zu sehen.

• Eine Turing-Maschine ist eine Maschine mit "beweglichen Teilen" und Maschinen arbeiten , was einer Energiemessung entspricht , und sie haben Zeit- / Raummessungen. Komplexitätsklassen können daher als "Energie" angesehen werden, die mit Black-Box-Input-Output-Transformationen verbunden ist.

• Es gibt viele mögliche Analoga aus der Geschichte der Mathematik, z. B. das Problem der Quadratur des Kreises, der Suche nach algebraischen Lösungen für die Quintingleichung usw.

• Impaggliazos Welten

• Fortnows neues Buch enthält viele populärwissenschaftliche Analogien für den Bergbau.

• Verschlüsselung / Entschlüsselung: Turing hat während des Zweiten Weltkriegs berühmt dafür gearbeitet, und viele Theoreme, die Unterschiede in den Komplexitätsklassen belegen, scheinen möglicherweise mit Entschlüsselungsproblemen vergleichbar zu sein. Dies wird durch Papiere wie Natural Proofs verfestigt, bei denen die Trennung von Komplexitätsklassen in direktem Zusammenhang mit dem "Brechen" von Pseudozufallszahlengeneratoren steht.

• Komprimierung / Dekomprimierung: Unterschiedliche Komplexitätsklassen ermöglichen / repräsentieren unterschiedliche Datenkomprimierungsgrade. Angenommen, P / poly enthält NP. das würde bedeuten, dass es "kleinere" Einheiten (nämlich Schaltungen) gibt, die "größere" NP-Gesamtprobleme "codieren" können, dh die größeren (Daten-) Strukturen können effizient in kleinere (Daten-) Strukturen "komprimiert" werden.

• Entlang der Zoo / Tier-Analogie gibt es einen starken Blindmann- und Elefantenaspekt in der Komplexitätstheorie. Das Feld befindet sich anscheinend / möglicherweise noch in einem sehr langen Bogen (dies ist nicht unplausibel oder unerhört für andere mathematische Felder, die sich über Jahrhunderte oder sogar Jahrtausende erstrecken), und viel Wissen kann als partiell, disjunkt und unzusammenhängend angesehen werden fragmentiert.

Kurz gesagt, die Frage lautet "Optimismus in Verbindung mit Kürzungen". Wissenschaftler verzichten in ihrer rein logischen Suche meist auf Emotionen oder lachen sie manchmal sogar aus. Es besteht ein Gleichgewicht zwischen langfristigem Pessimismus und vorsichtigem Optimismus auf diesem Gebiet. Zwar besteht ein gewisser Spielraum für Informalität, doch sollten alle ernsthaften Forscher im Rahmen der Stellenbeschreibung auf Unparteilichkeit ihrer beruflichen Einstellungen hinarbeiten. Es ist verständlich, dass der Fokus auf kleinen Siegen und Inkrementalismus liegt und nicht "mitgerissen" wird.