Worst-Case bis durchschnittliche Fallreduzierungen

11

Gibt es Probleme, deren durchschnittliche Fallkomplexität mit der Worst-Case-Komplexität übereinstimmt? Was sind die zugrunde liegenden Eigenschaften dieser Probleme, die es ermöglichen, den schlimmsten Fall auf den Durchschnittsfall zu reduzieren?

Anonym
quelle
10
Zufällige Selbstreduzierbarkeit (Das ist eher eine Definition als eine zugrunde liegende Eigenschaft, aber ich vermute, der Wikipedia-Artikel gibt Ihnen einen guten Einstieg, um herauszufinden, was Sie wissen möchten.)
Peter Shor
1
@ PeterShor Kommentar -> Antwort?
Suresh Venkat

Antworten:

18

Diese Art von Problem war Gegenstand zahlreicher Studien. Sie können Referenzen finden, indem Sie zufällige Selbstreduzierbarkeit googeln , und der Wikipedia-Artikel ist ein guter Ort, um mit dem Lesen zu beginnen. Es gibt noch viele offene Fragen.

Peter Shor
quelle
15

Der Wikipedia-Eintrag, mit dem Peter verlinkt hat, erwähnt einige wichtige Beispiele für Probleme, bei denen es im schlimmsten Fall zu durchschnittlichen Fallreduzierungen kommt, wie zum Beispiel die permanente. Das kürzeste Vektorproblem (sowie damit verbundene Gitterprobleme) ist ein weiteres wichtiges Beispiel, siehe Ajtais Artikel und was danach kam (Arbeiten von Regev, Micciancio, Peikert, ...).

Eine der einzigen allgemeinen Beobachtungen, die wir in Bezug auf Probleme mit der Reduktion im ungünstigsten bis zum durchschnittlichen Fall haben, ist die folgende (begonnen mit der Arbeit von Feigenbaum und Fortnow ): (Zumindest bei nicht adaptiven Reduktionen) sind diese Probleme wahrscheinlich nicht vollständig für Klassen, die (wahrscheinlich) nicht unter Komplement geschlossen sind (z. B. sind sie wahrscheinlich nicht NP-vollständig).

NPcoNP

Dana Moshkovitz
quelle