Gibt es eine Erklärung für die Schwierigkeit, quadratische Untergrenzen für interessante NP-Probleme zu beweisen?

Dies ist eine Fortsetzung meiner vorherigen Frage:

Bekannteste deterministische Zeitkomplexitätsuntergrenze für ein natürliches Problem in NP

Ich finde es verwirrend, dass wir keine quadratische deterministische Zeituntergrenze für ein interessantes NP-Problem nachweisen konnten, für das sich die Leute interessieren, und versuchen, bessere Algorithmen zu entwerfen. Unsere Vermutung der Exponential Time Hypothesis besagt, dass SAT nicht in subexponentieller deterministischer Zeit gelöst werden kann, aber wir können nicht einmal beweisen, dass SAT (oder ein anderes interessantes NP-Problem) quadratische Zeit benötigt!

Ich weiß, interessant ist etwas subjektiv und vage. Ich habe keine Definition. Aber lassen Sie mich versuchen zu beschreiben, was ich für ein interessantes Problem halte: Ich spreche von Problemen, die nicht wenige Menschen interessant finden. Ich spreche nicht von isolierten Problemen, die hauptsächlich dazu dienen, eine theoretische Frage zu beantworten. Wenn die Leute nicht versuchen, schnellere Algorithmen für ein Problem zu finden, ist dies ein Hinweis darauf, dass das Problem nicht so interessant ist. Wenn Sie konkrete Beispiele für interessante Probleme wünschen, berücksichtigen Sie die Probleme in Karps Artikel von 1972 oder in Garey und Johnson 1979 (die meisten davon).

Gibt es eine Erklärung dafür, warum wir keine quadratische deterministische Zeituntergrenze für ein interessantes NP-Problem nachweisen konnten?

Hier ist eine Erklärung aus Liptons Blog: Köder und Schalter: Warum sind untere Grenzen so schwer?

$n^2$

Rudichs Einsicht erklärt, warum ein Beweis der unteren Grenze, dass er auf der folgenden Methode basiert, nicht funktionieren kann.

$f$$f$

Grundsätzlich gibt es kein Maß für den Fortschritt, der den Köder- und Schaltertrick von Rudich überleben kann und erfolgreich zu einer Untergrenze führt.

Eine andere Ansicht des Arguments "Köder und Schalter" finden Sie im Kapitel über natürliche Beweise von Arora-Barak. Sie verwenden dasselbe Argument, um zu argumentieren, dass ein Argument der unteren Grenze im Stil eines "formalen Komplexitätsmaßes" für Zufallsfunktionen mit hoher Wahrscheinlichkeit gelten muss. Aber wenn ein formales Komplexitätsmaß

1. weist einer Zufallsfunktion eine hohe Komplexität zu
2. weist einer einfachen Funktion keine hohe Komplexität zu
3. kann leicht aus der Wahrheitstabelle einer Funktion berechnet werden

dann kann es verwendet werden, um Pseudozufallsgeneratoren zu brechen. Dies ist informell die Barriere für natürliche Beweise. Wir haben argumentiert, dass 1. für viele Ansätze zur Untergrenze sehr vernünftig ist, ohne dass 2. das Komplexitätsmaß nutzlos erscheint, und 3. auf der Beobachtung basiert, dass es uns gelungen ist, die meisten kombinatorischen Existenzbeweise in effiziente Algorithmen umzuwandeln, und dass Intuition, dass ein von Natur aus nicht konstruktiver Beweis schwer zu entwickeln ist.

$C$$C'$$C'$$C$