Gibt es Probleme ohne effiziente Algorithmen, bei denen Existenzsätze bewiesen haben, dass solche Algorithmen existieren müssen?

22

Gibt es in CS Probleme, bei denen keine effizienten Algorithmen bekannt sind, obwohl es Theoreme gibt, die beweisen, dass solche effizienten Algorithmen existieren müssen?

Wie heißen diese Probleme? Wo kann ich mehr erfahren?

ds.algorithms reference-request terminology z5h
quelle
4
Ich denke, das ist relevant: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms
Philip White
3
Was ist deine Frage? Im Titel steht "Lösungen", aber im Inhalt schreiben Sie "Algorithmen".
Marcos Villagra
6
Ich denke, es ist besser, wenn Sie nach interessanten / natürlichen Problemen fragen , andernfalls ist es einfach, solche Probleme zu definieren: Nehmen Sie eine mathematische Aussage, von der nicht bekannt ist, dass sie wahr oder falsch ist, und geben Sie das Problem als Ausgabe 1 (unabhängig von der Eingabe) aus, wenn dies der Fall ist true und 0, wenn es falsch ist. Es gibt zwei sehr einfache Algorithmen, von denen einer dieses Problem löst. Die Entscheidung darüber, welche die mathematische Aussage im Grunde beweist / widerlegt, lässt sich also nicht treffen.
Kaveh

Antworten:

9

Als Beispiel verwendet Shelby Kimmel die in diesem Artikel beschriebene Methode des Gegners, um zu zeigen, dass für ein bestimmtes Problem, für das wir keine konstante Abfragelösung kennen, ein -Abfragealgorithmus existieren muss . Sie tut dies auf besonders raffinierte Weise, indem sie die Abfragekomplexität des mit sich selbst zusammengesetzten Problems mal findet und dann die Abfragekomplexität der kompostierten Funktion findet und feststellt, dass die Abfragekomplexität der ursprünglichen Funktion die Ordnung .O(1)dQ.Q.1d

Artem Kaznatcheev
quelle
12

Sicher, es gibt viele Beispiele, zumindest im Sinne Ihrer Frage.

Oft ergibt sich ein solches Ergebnis aus der probabilistischen Methode . Ein Artikel, der mir gefällt und auf den das Problem stößt, befasst sich beispielsweise mit der Rekonstruktion von Diagrammen im additiven Modell . Hier zeigen die Autoren, dass es eine Reihe von -Abfragen gibt, mit denen das Zieldiagramm (optimal) gelernt werden kann. Bei dieser Menge ist der Algorithmus effizient. Sie verwenden jedoch die probabilistische Methode, um die Existenz dieser kleinen Menge (für jede Problemgröße) zu zeigen, die für alle Eingaben funktioniert, diese jedoch nicht explizit erstellt. Das Beste, was sie tun können, ist nur eine Brute-Force-Suche durch eine exponentielle Familie von Abfragen, da sie keine explizite Konstruktion haben.O(dn)

Lev Reyzin
quelle
2

Nein, Sie können immer den schnellsten und den kürzesten Algorithmus für alle genau definierten Probleme verwenden . ;)

Marcus Ritt
quelle
Ich war nicht ganz ernst, aber ich beobachte, dass Hutters Konstruktion tatsächlich die Korrektheit des Algorithmus beweist. Warum wird die Frage Ihrer Meinung nach nicht beantwortet?
Marcus Ritt
4
@ Ross Snider: Natürlich entziehen sich unentscheidbare Sprachen Hutters Ergebnis: Er gibt schließlich einen Algorithmus! Anders als bei der Levin-Suche, bei der die Probleminstanzen über überprüfbare Zertifikate verfügen (wie bei der NP-Suche), ist dies bei der Hutter-Suche nicht der Fall. Es ist lediglich erforderlich, dass das Problem in einer formalen Sprache angegeben wird, die als Grundlage für die erschöpfende Suche nach Beweisen dienen kann [dass einige TM tatsächlich das angegebene Problem lösen]. Hutter / Levin gibt uns auch keine Existenznachweise für effiziente Algorithmen für ein Problem, es sei denn, wir wissen bereits, dass das Problem einen solchen Algorithmus hat.
Joshua Grochow
1
@Joshua Ich brachte unbestreitbare Sprachen als Beispiel für etwas auf, das Hutter / Levin nicht sicher entscheiden konnte (ich habe versucht, etwas Offensichtliches auszuwählen), das aber "gut definiert" bleibt. es ist ein Argument gegen die Behauptung, die im Titel des Papiers geführt wird. Natürlich gab ich zu, dass ich den Inhalt nicht gelesen hatte, was ich jetzt tun muss.
Ross Snider
1
Ist dieser Algorithmus der rechnerische Inhalt der Äquivalenz von konstruktiver und klassischer Mathematik für alle existierenden Aussagen?
Neel Krishnaswami
1
@Neel Kirshnaswami: Es ist schwer zu sagen, da ich nicht wusste, dass es eine solche Äquivalenz gibt! Können Sie einen Hinweis geben?
Joshua Grochow
1

Bearbeiten: In der folgenden Antwort wird das Vorhandensein von Lösungen für ein bestimmtes Rechenproblem und nicht das Vorhandensein von Algorithmen erneut überprüft. Anfangs habe ich die Frage falsch interpretiert.

Antworten

Es gibt eine Komplexitätsklasse, die diese Art von Rechenproblemen erfasst. Es ist als TFNP bekannt . Es wurde in diesem Papier definiert:

Nimrod Megiddo und Christos Papadimitriou. Über Gesamtfunktionen, Existenzsätze und rechnerische Komplexität . Theoretical Computer Science 81 (2): 317 & ndash; 324.

Hier finden Sie Probleme wie das Trichromatische Dreieck, für die die Existenz einer Lösung durch Sperner's Lemma garantiert wird (siehe das Papier für die Definition dieses Problems).

Sie haben auch das folgende Papier:

Christos Papadimitriou. Über die Komplexität des Paritätsarguments und andere ineffiziente Existenznachweise . Journal of Computer and Systems Science 48 (3), 1990.

In diesem Artikel finden Sie:

  • n
  • Gleichgewicht von 2-Spieler-Spielen.
  • Suchen Sie einen zweiten Hamilton-Pfad in einem Diagramm.

Das Papier enthält viele Beispiele für diese Art von Problemen. Also empfehle ich, sich das mal anzuschauen.

Marcos Villagra
quelle
2
Die Frage bezieht sich nicht auf Probleme mit nachweislich vorhandenen Lösungen für ihre Entscheidungsversionen, sondern auf Probleme mit der nachgewiesenen Existenz effizienter Algorithmen. Das sind verschiedene Dinge. Ich bin damit einverstanden, dass der Titel auf den ersten Blick irreführend sein kann. Allerdings nur auf den ersten Blick.
Oleksandr Bondarenko
Ja, ich stimme auch zu. Aber die Frage hat mich total in die Irre geführt. In diesem Fall ist die Antwort irreführend. Was mache ich? Lösche ich die frage Oder bearbeiten und warnen, was genau beantwortet wird?
Marcos Villagra
Es gibt keine Richtlinien zum Löschen von Antworten. Sie können immer das tun, was Sie für angemessen erachteten. Persönlich finde ich es in Ordnung, Ihre Antwort hier zu hinterlassen. Sie können eine Aussage darüber machen, welche Frage Sie genau beantworten.
Hsien-Chih Chang 張顯 之