Tardos-Funktion Gegenbeispiel zu Blums

In diesem Thread wird Norbet Blums versuchter $P \neq NP$ Beweis kurz widerlegt, indem festgestellt wird, dass die Tardos-Funktion ein Gegenbeispiel zu Satz 6 ist.

Satz 6 : Sei $f \in \mathcal{B}_n$ eine monotone Boolesche Funktion. Angenommen, es gibt einen CNF-DNF-Approximator $\mathcal{A}$ dem eine Untergrenze für $C_m(f)$ . Dann kann $\mathcal{A}$ auch verwendet werden, um die gleiche Untergrenze für zu beweisen $C_{st}(f)$.

Hier ist mein Problem: Die Tardos-Funktion ist keine Boolesche Funktion. Wie erfüllt sie also die Hypothesen von Satz 6?

In dieser Arbeit diskutieren sie die Komplexität der Funktion $\varphi(X) \leq f(v)$ , die im Allgemeinen keine monotone Boolesche Funktion ist, da zunehmende Kanten $\varphi(X)$ größer machen können, um $\varphi(X) \leq f(v)$ falsch , wenn es wahr ist mit weniger $1$ ‚s in der Eingabe. Die Funktion $\varphi(X) \geq f(v)$ berechnet im Allgemeinen nicht $1$ für $T_1$und auf T $0$$T_0$ .

Tatsächlich werden die Testsätze und T 0 genau so gewählt, dass die Berechnung von 1 für T 1 und 0 für T 0 mit Monotonie Ihre Funktion zur genauen Berechnung von CLIQUE bedeutet (sie definieren die Grenze zwischen 1 und $T_1$$T_0$$1$$T_1$$0$$T_0$$1$$0$ s in das Gitter der Eingaben), so implizieren diese Bemerkungen, dass die Tardos-Funktion die gleiche ist wie CLIQUE, was eindeutig nicht wahr ist.

Trotzdem behaupten so viele Leute - und so kenntnisreiche Leute - dass die Tardos-Funktion ein unmittelbares Gegenbeispiel ist, also muss es etwas geben, das mir fehlt. Könnten Sie bitte eine ausführliche Erklärung oder einen Beweis für diejenigen von uns liefern, die interessiert sind, aber nicht ganz auf Ihrem Niveau sind?

diese Bemerkungen implizieren also, dass die Tardos-Funktion dieselbe ist wie CLIQUE.$f$

Kurze Antwort - NEIN.

Es ist nur eine monotone "clique-like": akzeptiert alle cliques und lehnt alle vollständigen ( k - 1 ) -partiten Graphen ab. Es können jedoch einige von CLIQUE abgelehnte Graphen akzeptiert werden: Graphen G mit ω ( G ) < k, aber χ ( G ) ≥ k (sogenannte "nicht perfekte" Graphen). Das$k$$(k-1)$$G$$\omega(G) < k$$\chi(G)\geq k$ Papier von Grötschel, Lovász und Schrijver bedeutet , dass hat eine nicht-monotone Schaltung von Polynom Größe. Aber nach Satz 6 im "Beweis" ,$f$ jederMonotone Clique-ähnliche Boolesche Funktion erfordert nicht-monotone Schaltkreise mit superpolynomieller Größe. Eines dieser beiden Papiere muss also falsch sein. Das Papier GLS-1981 stand schon seit> 35 Jahren ...

Was Tardos tut, ist das Folgende. Sie geht von der Graphenfunktion , wobei ϑ die berühmte Lovász'sche Theta-Funktion ist. Die Grundtatsache ist , daß die Zahl φ ( G ) zwischen der Clique Nummer und der chromatischen Anzahl sandwichartig angeordnet ist: ω ( G ) ≤ φ ( G ) ≤ & khgr; ( G ) . Sie benutzt dann die Tatsache, dass ϑ ( G $\varphi(G):=\vartheta(\overline{G})$$\vartheta$$\varphi(G)$$\omega(G)\leq \varphi(G)\leq \chi(G)$$\vartheta(G)$ kann in Polynomzeit angenähert werden. Darauf aufbauend definiert sie eine Graphfunktion mit folgenden Eigenschaften:$\phi(G)$

1. Werte von können in Polynomzeit (in der Anzahl n der Eckpunkte) berechnet werden . $\phi(G)$$n$
2. ist monoton: Das Hinzufügen von Kanten kann nur den Wert erhöhen. $\phi$
3. gilt für alle Graphen G . $\omega(G)\leq \phi(G)\leq \chi(G)$$G$

Dann definiert sie (wie Clement C. bemerkt) die gewünschte monotone Boolesche Funktion als: f ( G ) = 1 iff ϕ ( G ) ≥ k . Nach (1) hat die Funktion eine (nicht monotone) Schaltung von polynomischer Größe. Nach (2) ist f eine monotone Boolesche Funktion. Mit (3) akzeptiert f alle k- Klassen und lehnt alle vollständigen ( k - 1 ) -Partit-Graphen ab. $f$$f(G)=1$$\phi(G)\geq k$$f$$f$$k$$(k-1)$

Sehen Sie hier für technische Details.