<blockquote>
<p>so these remarks imply that the Tardos function <span class="math-container">$f$</span> is the same as
CLIQUE.</p>
</blockquote>
<p>Short answer - NO.</p>
<p>
It is only a *monotone* "clique-like": accepts all <span class="math-container">$k$</span>-cliques, and rejects all  complete <span class="math-container">$(k-1)$</span>-partite graphs. It can, however, accept some graphs rejected by CLIQUE: graphs <span class="math-container">$G$</span> with <span class="math-container">$\omega(G) &lt; k$</span> but <span class="math-container">$\chi(G)\geq k$</span> (so-called "non-perfect" graphs). The [paper](https://link.springer.com/article/10.1007/BF02579273) by Grötschel,
Lovász and Schrijver implies that <span class="math-container">$f$</span> <b>has</b> a non-monotone circuit of polynomial size. But, according to Theorem 6 in the ["proof"](https://arxiv.org/abs/1708.03486), <b>any</b> monotone clique-like Boolean function requires non-monotone circuits of super-polynomial size. 
So, one of these two papers <b>must</b> be wrong. The GLS-1981 paper stood for already > 35 years  ...
<p>
What Tardos does is the following. She starts from the graph function <span class="math-container">$\varphi(G):=\vartheta(\overline{G})$</span>, where <span class="math-container">$\vartheta$</span> is the famous Lovász' theta-function. The fundamental fact is that the number
<span class="math-container">$\varphi(G)$</span> is sandwiched between the clique number and the chromatic number: <span class="math-container">$\omega(G)\leq \varphi(G)\leq \chi(G)$</span>. 
She then uses the fact that <span class="math-container">$\vartheta(G)$</span> can be approximated in polynomial time. Based on this, she defines a graph-function <span class="math-container">$\phi(G)$</span> with the following properties:
<ol>
<li> Values of <span class="math-container">$\phi(G)$</span> can be computed in polynomial time (in the number <span class="math-container">$n$</span> of vertices).
<li> <span class="math-container">$\phi$</span> is monotone: adding edges can only increase its value.
<li> <span class="math-container">$\omega(G)\leq \phi(G)\leq \chi(G)$</span> holds for all graphs <span class="math-container">$G$</span>.
</ol>
Then (as Clement C. notes) she defines the desired monotone Boolean function <span class="math-container">$f$</span> as: <span class="math-container">$f(G)=1$</span> iff <span class="math-container">$\phi(G)\geq k$</span>. By (1), the function has a (non-monotone) circuit of polynomial size. By (2), <span class="math-container">$f$</span> is a monotone Boolean function. By (3), 
<span class="math-container">$f$</span> accepts all <span class="math-container">$k$</span>-cliques, and rejects all complete <span class="math-container">$(k-1)$</span>-partite graphs.
<p>
See [here](https://web.vu.lt/mif/s.jukna/boolean/tardos.html) for technical details. 

CC BY-SA 3.0
2017-08-25T18:55:47.887Z
The GLS-1981 paper is [here](https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf) for free. 
This paper, in turn, is based on Khachiyan-1979 elipsoid paper. So, (at least) one of these three papers must be wrong?
Tobias Müller
CC BY-SA 3.0
2017-08-26T19:22:40.127Z
@Tobias: well, we are pretty sure that these two > 35 old papers are correct (so many times reproduced in lectures, somebody would already have observed an error). The problem with the current "proof" is that it is "by construction", not "by an argument" (as in the two mentioned papers). It is then dammed difficult to point to a *specific* place, where the "construction" fails. Especially when the "construction" is *so* imprecise. This is why I think it is now the DUTY of the author, not of us, to point to this place (where Tardos doesn't go through his construction.)
Stasys
CC BY-SA 4.0
2017-08-24T16:02:25.230Z
2021-12-16T10:01:01.727Z
2021-12-16T10:01:01.727Z
Stasys
<p>In <a href="https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct">this thread</a>, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.</p>

<p><strong>Theorem 6</strong>: 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)$.</p>

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

<p>In <a href="http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf" rel="noreferrer">this paper</a>, 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$.</p>

<p>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.</p>

<p>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. <strong>Could you please provide a detailed explanation or proof for those of us who are interested parties but not quite on your level?</strong></p>

CC BY-SA 3.0
2017-08-23T13:56:38.380Z
A good source would be [Jukna's book](http://www.thi.cs.uni-frankfurt.de/~jukna/boolean/), p.272 (just before Theorem 9.28). Given the (non-Boolean) function $\phi$, consider the Boolean function $f_\phi$ which is the thresholding of $\phi$: $$f_\phi(G) = \begin{cases} 1 & \text{if } \phi(G) \geq \sqrt{n}\\ 0&\text {otherwise}\end{cases}$$ The result then applies.
Clement C.
CC BY-SA 3.0
2017-08-23T14:31:17.750Z
So, to be clear, you're telling me that $f_\phi(G)$ will evaluate to $1$ on cliques of size $\sqrt{n}$ and $0$ on graphs of $n$ vertices induced by proper $\lfloor \sqrt{n}-1 \rfloor$ colorings?
user144527
CC BY-SA 3.0
2017-08-23T16:24:04.710Z
Of course, ths does not hold for *any* $\phi$. But Tardos' function $f_{\phi}$ is based on a monotone graph-function $\phi$ satisfying $\omega(G)\leq \phi(G)\leq \chi(G)$. So, thresholding $f_{\phi}$ of $\phi$ does exactly what you say. See the end of Section 9.8 [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Chapter9.pdf).
Stasys
CC BY-SA 3.0
2017-08-23T16:31:42.073Z
Ah, I see. The set $T_0$ was not what I thought. It's only composed of the graphs with $\chi < k$, and, importantly, *not* all the graphs with $\chi >= k$ but without cliques of size $k$, some of which are on the lattice boundary of the monotone function, where $k = \lfloor \sqrt{n} \rfloor$.
user144527
CC BY-SA 3.0
2017-08-23T17:39:47.883Z
Right. B.t.w. I actually do not understand why people are down-voting your (eligible in view of all this noise around this "proof") question? It is now the author's of this P!=NP claim turn: explain why the "proof" will NOT work for Tardos' function. Point to page X and line(s) Y in the paper. Hint: the bug will be in upper-bounding the number of errors introduced during the approximation (negations can annihilate lots of previously "valid" terms). Otherwise (no explanation) = no "proof".
Stasys
CC BY-SA 3.0
2017-08-24T02:05:57.170Z
@Stasys, your first comment can be an answer.
Kaveh
<cc.complexity-theory><np-hardness><complexity-classes>
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
user144527
# Tardos Function Counterexample to Blum's $P\neq NP$ Claim

(Asked by: username_0 on 2017-08-23)

In [this thread](https://cstheory.stackexchange.com/questions/38803/is-norbert-blums-2017-proof-that-p-ne-np-correct), 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](http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf), 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?**

**Tags:** cc.complexity-theory, np-hardness, complexity-classes

> **Comments:**
> **username_1**: A good source would be [Jukna's book](http://www.thi.cs.uni-frankfurt.de/~jukna/boolean/), p.272 (just before Theorem 9.28). Given the (non-Boolean) function $\phi$, consider the Boolean function $f_\phi$ which is the thresholding of $\phi$: $$f_\phi(G) = \begin{cases} 1 & \text{if } \phi(G) \geq \sqrt{n}\\ 0&\text {otherwise}\end{cases}$$ The result then applies.  
> **username_0**: So, to be clear, you're telling me that $f_\phi(G)$ will evaluate to $1$ on cliques of size $\sqrt{n}$ and $0$ on graphs of $n$ vertices induced by proper $\lfloor \sqrt{n}-1 \rfloor$ colorings?  
> **username_2**: Of course, ths does not hold for *any* $\phi$. But Tardos' function $f_{\phi}$ is based on a monotone graph-function $\phi$ satisfying $\omega(G)\leq \phi(G)\leq \chi(G)$. So, thresholding $f_{\phi}$ of $\phi$ does exactly what you say. See the end of Section 9.8 [here](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Chapter9.pdf).  
> **username_0**: Ah, I see. The set $T_0$ was not what I thought. It's only composed of the graphs with $\chi < k$, and, importantly, *not* all the graphs with $\chi >= k$ but without cliques of size $k$, some of which are on the lattice boundary of the monotone function, where $k = \lfloor \sqrt{n} \rfloor$.  
> **username_2**: Right. B.t.w. I actually do not understand why people are down-voting your (eligible in view of all this noise around this "proof") question? It is now the author's of this P!=NP claim turn: explain why the "proof" will NOT work for Tardos' function. Point to page X and line(s) Y in the paper. Hint: the bug will be in upper-bounding the number of errors introduced during the approximation (negations can annihilate lots of previously "valid" terms). Otherwise (no explanation) = no "proof".  
> **username_3**: @username_2, your first comment can be an answer.  

---

## 1 answers

### Answer by username_2 on 2017-08-24. Score: 20

> 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).- $\phi$ is monotone: adding edges can only increase its value.- $\omega(G)\leq \phi(G)\leq \chi(G)$ holds for all graphs $G$.

Then (as username_1 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.

> **Comments:**
> **username_4**: The GLS-1981 paper is [here](https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1981a.pdf) for free.  This paper, in turn, is based on Khachiyan-1979 elipsoid paper. So, (at least) one of these three papers must be wrong?  
> **username_2**: @Tobias: well, we are pretty sure that these two > 35 old papers are correct (so many times reproduced in lectures, somebody would already have observed an error). The problem with the current "proof" is that it is "by construction", not "by an argument" (as in the two mentioned papers). It is then dammed difficult to point to a *specific* place, where the "construction" fails. Especially when the "construction" is *so* imprecise. This is why I think it is now the DUTY of the author, not of us, to point to this place (where Tardos doesn't go through his construction.)  

---

