Tardos Function Counterexample to Blum's $P\neq NP$ Claim

Question

In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.

Theorem 6: Let $f \in \mathcal{B}_n$ be any monotone Boolean function. Assume that there is a CNF-DNF-approximator $\mathcal{A}$ which can be used to prove a lower bound for $C_m(f)$. Then $\mathcal{A}$ can also be used to prove the same lower bound for $C_{st}(f)$.

Here's my problem: the Tardos function is not a Boolean function, so how does it satisfy the hypotheses of Theorem 6?

In this paper, they discuss the complexity of the function $\varphi(X) \leq f(v)$, which is not in general a monotone Boolean function, since increasing edges can make $\varphi(X)$ larger to make $\varphi(X) \leq f(v)$ false when it was true with fewer $1$'s in the input. The function $\varphi(X) \geq f(v)$ does not, in general, compute $1$ on $T_1$ and $0$ on $T_0$.

In fact, the test sets $T_1$ and $T_0$ are chosen precisely so that computing $1$ on $T_1$ and $0$ on $T_0$ with monotonicity means your function in precisely computing CLIQUE (they define the boundary of the $1$'s and $0$'s in the lattice of inputs), so these remarks imply that the Tardos function is the same as CLIQUE, which is clearly not true.

Yet, so many people -- and such knowledgeable people -- claim that the Tardos function provides an immediate counterexample, so there must be something I'm missing. Could you please provide a detailed explanation or proof for those of us who are interested parties but not quite on your level?

Answer 1

so these remarks imply that the Tardos function $f$ is the same as CLIQUE.

Short answer - NO.

It is only a *monotone* "clique-like": accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs $G$ with $\omega(G) < k$ but $\chi(G)\geq k$ (so-called "non-perfect" graphs). The [paper](https://link.springer.com/article/10.1007/BF02579273) by Grötschel, Lovász and Schrijver implies that $f$ has a non-monotone circuit of polynomial size. But, according to Theorem 6 in the ["proof"](https://arxiv.org/abs/1708.03486), any monotone clique-like Boolean function requires non-monotone circuits of super-polynomial size. So, one of these two papers must be wrong. The GLS-1981 paper stood for already > 35 years ...

What Tardos does is the following. She starts from the graph function $\varphi(G):=\vartheta(\overline{G})$, where $\vartheta$ is the famous Lovász' theta-function. The fundamental fact is that the number $\varphi(G)$ is sandwiched between the clique number and the chromatic number: $\omega(G)\leq \varphi(G)\leq \chi(G)$. She then uses the fact that $\vartheta(G)$ can be approximated in polynomial time. Based on this, she defines a graph-function $\phi(G)$ with the following properties:

1. Values of $\phi(G)$ can be computed in polynomial time (in the number $n$ of vertices).
2. $\phi$ is monotone: adding edges can only increase its value.
3. $\omega(G)\leq \phi(G)\leq \chi(G)$ holds for all graphs $G$.

Then (as Clement C. notes) she defines the desired monotone Boolean function $f$ as: $f(G)=1$ iff $\phi(G)\geq k$. By (1), the function has a (non-monotone) circuit of polynomial size. By (2), $f$ is a monotone Boolean function. By (3), $f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs.

See [here](https://web.vu.lt/mif/s.jukna/boolean/tardos.html) for technical details.