Probleme, die in der Praxis nicht intuitiv lösbar sind?

Vor kurzem habe ich die schmerzhafte lustige Erfahrung gemacht, einem jungen talentierten Autodidakten, der noch nie einen formalen Kurs in Algorithmen oder Komplexität belegt hat, informell das Konzept der Computerkomplexität zu erklären. Es überrascht nicht, dass viele Begriffe zunächst seltsam wirkten, aber mit einigen Beispielen (PTIME, Unlösbarkeit, Unberechenbarkeit) Sinn machten , während andere natürlicher zu sein scheinen (Problemklassifizierung über Reduktionen, Zeit und Raum als Ressourcen, asymptotische Analyse) . Alles lief großartig, bis ich versehentlich zugab, dass SATkann effizient gelöst werden * in der Praxis ... Und einfach so habe ich sie verloren. Es war egal, wie überzeugend ich versuchte, für die Theorie zu argumentieren, der Junge war überzeugt, dass es alles künstliche Mistmathematik war , für die er sich nicht interessieren sollte. Gut...

¯ \ _ (ツ) _ / ¯

Nein, mir war weder das Herz gebrochen, noch interessierte es mich wirklich, was er dachte, das ist nicht der Punkt dieser Frage. Bei unserem Gespräch musste ich über eine andere Frage nachdenken.

Wie viel weiß ich wirklich über Probleme, die theoretisch nicht lösbar sind (superpolynomielle Zeitkomplexität), aber praktisch lösbar sind (über Heuristiken, Approximationen, SAT-Löser usw.)?

Mir wurde nicht viel klar. Ich weiß, dass es einige sehr effiziente SAT-Löser gibt, die enorme Instanzen effizient lösen, die Simplex in der Praxis hervorragend funktioniert und vielleicht ein paar weitere Probleme oder Algorithmen. Können Sie mir helfen, ein vollständigeres Bild zu zeichnen? Welche bekannten Probleme oder gar Problemklassen fallen in diese Kategorie?

TL; DR: Was sind Probleme, die in der Praxis kontraintuitiv lösbar sind? Gibt es eine (aktualisierte) Ressource, um mehr zu lesen? Haben wir eine Charakterisierung für sie? Und schließlich, als allgemeine Diskussionsfrage, sollten wir nicht?

EDIT # 1: Um meine letzte Diskussionsfrage zu einer solchen Charakterisierung zu beantworten , wurde ich in die geglättete Analyse von Algorithmen eingeführt, ein Konzept, das von Daniel Spielman und Shang-Hua Teng in [1] eingeführt wurde und kontinuierlich zwischen dem Worst-Case und interpoliert Durchschnittsfallanalysen von Algorithmen. Es ist nicht genau die oben diskutierte Charakterisierung, aber es fängt das gleiche Konzept ein, und ich fand es interessant.

[1] Spielman, Daniel A. und Shang-Hua Teng. "Geglättete Analyse von Algorithmen: Warum der Simplex-Algorithmus normalerweise polynomielle Zeit benötigt." Zeitschrift der ACM (JACM) 51, nr . 3 (2004): 385 & ndash; 463.

• In der Praxis lassen sich häufig stark strukturierte SAT-Instanzen (auch auf Millionen von Variablen) lösen. Es sind jedoch noch zufällige SAT-Instanzen in der Nähe der Erfüllbarkeitsschwelle mit nur ein paar hundert Variablen offen (was bedeutet, dass Sie selbst in der Praxis, wenn Sie so etwas generieren, im Leben des Universums möglicherweise nie wissen, ob das von Ihnen generierte Objekt erfüllbar ist oder nicht) mit aktuellen SAT-Lösern). Diese verwandte Frage und ihre Antworten könnten Sie interessieren .

• Clique Finder sind auch "in der Praxis" schockierend gut

  • In Bezug auf Clique Finder wird (ein Teil der) Erklärung durch eine Durchschnittsfallanalyse der fraglichen Algorithmen gegeben.

    Sehen https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• Integer-Programmierung und Mixed Integer-Linear-Programmierung (mit einigen rationalen und einigen ganzzahligen Variablen) stehen im Mittelpunkt ganzer Operations Research-Abteilungen und können in der Praxis oft (aber nicht immer) gelöst werden

• $\mathsf{PSPACE}$$\mathsf{PSPACE}$ -komplette Problem.)

• $\mathsf{EXPSPACE}$ -komplette!

• Wie bereits in den Kommentaren von DW ausgeführt, kann der Graph-Isomorphismus praktisch gelöst werden. Es ist sehr schwer, moderne GI-Software wie Nauty, Bliss, Saucy usw. zu überlisten.

Der Hindley-Milner Typ-System wird in funktionalen Programmiersprachen (Haskell, SML, OCaml) verwendet. Der Typ-Inferenz-Algorithmus ist in der Praxis nahezu linear und funktioniert erstaunlich gut, ist jedoch als DEXPTIME-vollständig bekannt!

Ein allgemeiner Kommentar: Es ist keine Überraschung, dass die Komplexität der schlechtesten Zeit nicht unbedingt ein sehr gutes Maß für die praktische Leistung eines Algorithmus ist. Zu sagen, dass die Diskrepanz zwischen Theorie und Praxis die Komplexitätstheorie unbrauchbar macht, ist wie zu sagen, dass natürliche Zahlen eine Verschwendung sind, weil wir nur eine winzige Menge aller verfügbaren Zahlen verwenden. Ein berühmter Philosoph sagte einmal: "Erfahrung ohne Theorie ist blind, aber Theorie ohne Erfahrung ist nur ein intellektuelles Spiel."

Weitere Beispiele, hauptsächlich aus Programmiersprachen:

1. k-CFA (k-Control Flow Analysis) ist EXPTIME-vollständig (Van Horn & Mairson 2008), aber Compiler wie MLton, die das gesamte Programm optimieren, führen es trotzdem aus. Die Kompilierungszeiten sind lang, aber selten katastrophal.
2. Das Auflösen (dynamischer) Überlastungen ist in der Regel NP-vollständig (Palsberg 2012). In der realen Welt ist dies jedoch selten ein Problem.
3. $k$
4. Das Lösen von SMTs ist in der Regel NP-vollständig, kommerzielle SMT-Löser (wie Z3 und CVC4) sind jedoch in der Regel recht leistungsfähig. Ich arbeite nicht direkt mit SMT-Solvern, aber ich habe Z3 indirekt von Liquid Haskell und Dafny verwendet, und die Überprüfungszeiten scheinen in Ordnung zu sein.
5. Das Entscheidungsproblem für die Presburger-Arithmetik ist sehr komplex (Fischer & Rabin 1974), aber der Entscheidungsalgorithmus von Bill Pugh, der Omega-Test (Pugh 1991), läuft im Allgemeinen innerhalb der Polynomzeit niedriger Ordnung.

$O$$n$$n$

Verweise:

[1] David Van Horn und Harry G. Mairson. 2008. Die Entscheidung für kCFA ist für EXPTIME abgeschlossen. In Proceedings der 13. ACM SIGPLAN International Conference on Functional Programming (ICFP '08). ACM, New York, NY, USA, 275–282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer und MO Rabin. 1974. ÜBEREXPONENTIELLE KOMPLEXITÄT DER PRESBURGER-ARITHMETIK. Technischer Bericht. Massachusetts Institute of Technology, Cambridge, Massachusetts, USA.

[4] William Pugh. 1991. Der Omega-Test: Ein schneller und praktischer Algorithmus zur ganzzahligen Programmierung für die Abhängigkeitsanalyse. In Proceedings of the 1991 ACM / IEEE Konferenz über Supercomputing (Supercomputing '91). ACM, New York, NY, USA, 4-13.

neuronale Netze trainiert Gradientenabfallsaktualisierung Methoden wird auch als schlecht np-harte Problem erwiesen https://www.cs.utexas.edu/~klivans/crypto-hs.pdf sind aber in der Praxis im Allgemeinen lösbar.