Gibt es bekannte NP-Probleme, von denen vermutet wird, dass sie im Durchschnitt exponentiell schwer sind?

Die ETH gibt an, dass SAT im schlimmsten Fall in subexponentieller Zeit nicht gelöst werden kann. Was ist mit dem Durchschnittsfall? Gibt es natürliche Probleme in NP, von denen vermutet wird, dass sie im Durchschnitt exponentiell schwer sind?

Unter Durchschnittsfall versteht man die durchschnittliche Laufzeit mit gleichmäßiger Verteilung auf die Eingänge.

$2^{n^{1-o(1)}}$$2^{O(n/\log n)}$

$n$$cn$$c$

Es gibt mehrere Pseudozufallszahlengeneratoren, für die wir keine Polynomzeitalgorithmen zum Brechen haben. Ich denke, man könnte sie im Durchschnitt als schwierig betrachten. Schauen Sie sich die Generatoren unter www.ecrypt.eu.org/stream/ an. Es gibt natürlich auch andere, die Sie online recherchieren können.

Mein Verständnis ist, dass es zwar einige Kandidaten aus der Theorie der Unzerbrechlichkeit von Kryptographie und Zufallszahlengeneratoren gibt [z. B. einige, die in Razborov / Rudich, Natural Proofs, zitiert wurden], die meisten Aspekte Ihrer Frage jedoch von Experten als grundsätzlich wichtige "noch offene" Fragen anerkannt werden im Feld. Von der Einführung bis zur umfassenden Umfrage weist die durchschnittliche Fallkomplexität von Bogdanov und Trevisan (2006) einige verwandte Punkte auf. Hilfreich kann auch Trevisans Youtube-Vortrag über Ergebnisse und offene Fragen von durchschnittlicher Fallkomplexität sein.

$\neq$

$\neq$

Die richtigen Techniken, um eine solche Theorie auf natürliche Probleme und Verteilungen anzuwenden, wurden noch nicht entdeckt. Unter diesem Gesichtspunkt ähnelt der aktuelle Stand der Theorie der durchschnittlichen Fallkomplexität in NP dem Stand der Theorie der Unannäherbarkeit von NP-Optimierungsproblemen vor dem PCP-Theorem.