Probleme, die sich exponentiell anfühlen, aber P sind

12

Ich versuche, eine Liste von Algorithmen / Problemen zu erstellen, die "außergewöhnlich nützlich" sind, wie zum Beispiel das Lösen von Problemen, die von Natur aus sehr exponentiell erscheinen, aber einige besonders clevere Algorithmen haben, die sie letztendlich lösen. Beispiele für das, was ich meine:

  • Lineare Programmierung (Der Simplex-Algorithmus ist eine Exponentialzeit; es hat lange gedauert, bis eine Lösung für die Polynomzeit gefunden wurde!)
  • Allgemeiner gesagt, Semidefinite Programming
  • Primalitätstests
  • 2-SAT und HORNSAT
  • Determinanten berechnen (wenn dies nicht schwierig klingt, betrachten Sie die permanente)
  • Perfekte Übereinstimmungen finden
  • Eine Vielzahl von gruppentheoretischen Problemen, die mit der Klassifikation endlicher einfacher Gruppen gelöst werden können
  • Eine Vielzahl schwieriger Graphprobleme, die mit komplizierten Forbidden Minor-Charakterisierungen gelöst werden können (Einbettbarkeit auf einer beliebigen Oberfläche; Begrenzung von Baumbreite und Verzweigungsbreite; reduzierbare Delta-Wye-Graphen)
  • Berechnen von Exponentialen in einer begrenzten Gruppe (dh Berechnen von in Schritten, wie durch wiederholtes Quadrieren erreicht)einbmodkLog⁡b
  • Berechnungen, die auf dem LLL-Algorithmus beruhen. (Als Sonderfall: Euklidischer Algorithmus. Als allgemeinerer Fall: PSLQ- oder HJLS-Algorithmus.)
  • Einschränkungsprobleme ohne Taylor-Terme (?). Ich gebe zu, dass ich das nicht ganz verstehe, aber es hört sich so an, als würde es die obigen 2-SAT / HORNSAT-Fälle und jegliche lineare Algebra über endliche Felder subsumieren. Siehe hier für einen längeren Beitrag
  • Probleme berechenbar über holographische Reduktionen .

Als lobende Erwähnung möchte ich auch den Graphisomorphismus erwähnen, da er immer noch furchtbar einfach ist ( ) und so vielen anderen Isomorphismusproblemen entspricht:nLog2⁡n

  • Digraphen / Multigraphen / Hypergraphen (eine Art "schwierigeres" Problem)
  • Endliche Automaten / CFGs

Offensichtlich gibt es eine Reihe von Schwierigkeiten, aber alle lassen zumindest einige Menschen mit einem gewissen Gefühl der "Überraschung" zurück, in dem Sinne, dass das Problem schwierig klingen kann, sich aber als lösbar herausstellt. LP klingt vielleicht relativ unkompliziert, aber es hat einige Zeit gedauert, bis eine Lösung dafür gefunden wurde. Das wiederholte Quadrieren oder Lösen von 2-SAT ist etwas, das sich ein Student möglicherweise selbst einfallen lassen könnte. Wenn Sie jedoch nur von NP-Complete-Problemen erfahren hätten, ohne HORNSAT gesehen zu haben, könnte dies wie ein natürlicher Kandidat für die NP-Vollständigkeit klingen. Das Lösen des CFSG oder die polynomische Überprüfung der Delta-Wye-Reduzierbarkeit sind keine Kleinigkeiten.

Ich hoffe das macht Sinn; Hier gibt es natürlich viele subjektive Attribute, aber ich bin gespannt, was andere Leute für effiziente Lösungen für "offensichtlich schwierige" Probleme halten.

complexity-theory polynomial-time efficiency Alex Meiburg
quelle
Als Motivation für diese Frage (weil auch ein Freund gefragt hat): Wir reden oft darüber, wie wichtig es ist, Schüler über NP-Vollständigkeit und Unentscheidbarkeit zu unterrichten, weil sie erkennen können, wann Probleme zu schwer werden und sie diese vermeiden sollten. Diese Liste würde lauten: "Probleme, die Sie möglicherweise mit NP-Complete verwechseln, die Sie jedoch tatsächlich lösen können". Ich erwarte nicht, dass sich viele Schüler voll und ganz damit auskennen, dass Determinanten nicht berechnet werden können - so wie sie 3SAT in der Natur wahrscheinlich nicht begegnen werden -, aber sie sollten andere gleichwertige Probleme erkennen
Alex Meiburg
1
Ich vermute, dass dies zu weit gefasst ist, um zu unserer Website zu passen. Eine vollständige Liste von Dingen anzufordern, hört sich nicht nach der Art von Frage an, die hier gut funktioniert. "Ich bin neugierig zu hören, was andere Leute finden ..." klingt nach einer Frage, die hier nicht passt. Siehe unsere Hilfe .
DW
1
Ich verstehe, ich habe versucht, die Subjektivität in dieser Frage anzuerkennen, aber ich denke, diese Frage ist größtenteils etwas, auf das sich die Leute einigen und aus dem sie mit einer produktiven Diskussion lernen würden. Fragen, die den gewünschten Ton haben (obwohl ich eine andere Site kenne), finden Sie unter cstheory.stackexchange.com/questions/20930/… oder cstheory.stackexchange.com/questions/11119/… ?
Alex Meiburg
Außerdem ist überhaupt nicht klar, was sich für wen exponentiell anfühlt.
Raphael

Antworten:

2

Für mich ist einer der effizientesten Algorithmen der Blossom V-Algorithmus, der die perfekte Übereinstimmung des Maximalgewichts in einem allgemeinen Diagramm findet:

https://en.m.wikipedia.org/wiki/Blossom_algorithm

Dmitry Kamenetsky
quelle
1
Das ist ein gutes Beispiel! Ich hatte nie wirklich darüber nachgedacht oder es gebraucht und hatte den Eindruck, dass die maximale Übereinstimmung auf beliebigen Graphen NP-schwer war. :)
Alex Meiburg
1

Für mich sind alle klassischen und die neueren effizienteren Algorithmen zum Verifizieren oder Auffinden eines Minimum Spanning Tree (MST) eines verbundenen kantengewichteten Graphen gute Kandidaten. Viele dieser Algorithmen sind in Wikipedia aufgeführt .

Auf den ersten Blick sieht dieses Problem wie das Problem des Handlungsreisenden aus, eines der wenigen bekanntesten NP-harten Probleme. Am erstaunlichsten ist, dass es lineare Algorithmen gibt, mit denen ein MST verifiziert werden kann, und viele nahezu lineare Algorithmen, mit denen ein MST gefunden werden kann! Tatsächlich ist eines der bekanntesten offenen Probleme bei Algorithmen, ob es einen deterministischen linearen Algorithmus gibt, um eine MST in allgemeinen Graphen zu finden. Es stellt sich heraus, dass es eine Fülle von mathematischen und graphischen Strukturen und Eigenschaften sowie eine Vielzahl praktischer Anwendungen gibt, die mit MST verbunden sind, was es zu einem der unterhaltsamsten und erweiterbarsten Themen im Informatikkurs macht. Eine leicht veraltete, aber sehr gut geschriebene umfassende Einführung finden Sie im Tutorial von Jason Eisner .

John L.
quelle