22
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A good source would be Jukna's book, 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. $\endgroup$ – Clement C. Aug 23 '17 at 13:56
  • $\begingroup$ 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? $\endgroup$ – user144527 Aug 23 '17 at 14:31
  • 4
    $\begingroup$ 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. $\endgroup$ – Stasys Aug 23 '17 at 16:24
  • 4
    $\begingroup$ 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". $\endgroup$ – Stasys Aug 23 '17 at 17:39
  • 1
    $\begingroup$ @Stasys, your first comment can be an answer. $\endgroup$ – Kaveh Aug 24 '17 at 2:05
18
$\begingroup$

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 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", 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 for technical details.

$\endgroup$
  • 1
    $\begingroup$ The GLS-1981 paper is here for free. This paper, in turn, is based on Khachiyan-1979 elipsoid paper. So, (at least) one of these three papers must be wrong? $\endgroup$ – Tobias Müller Aug 25 '17 at 18:55
  • 3
    $\begingroup$ @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.) $\endgroup$ – Stasys Aug 26 '17 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.