Status of András Faragó’s (second) claimed proof that NP=RP

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1.

A few days ago, Faragó posted another claimed proof to the arXiv. Perhaps, given the first attempt, less attention will be paid to this second paper, but I still wonder whether any similar (or dissimilar) problems have been found.

• Ancient Greeks had a story that is pertinent to this situation. Dec 29, 2023 at 8:55
• The expression “Note that our sampling algorithm (if correct) has extremely surprising consequences” (emphasis mine) is not exactly inviting confidence. Dec 29, 2023 at 13:30
• Well, the author made a mistake once. Maybe he is just trying to be modest :) Dec 29, 2023 at 18:52
• To anybody wondering why the preprint was not retracted: I wrote to Faragó, but I believe he must have been quite ill by that point, and it seems that he has now, sadly, died. Feb 6 at 18:58

It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version.

Theorem 1 seems to say the following, at least in a special case. Let $$S$$ be some finite domain and let $$H\subset S$$ denote some subset. Let $$X$$ be a random $$n\times n$$ array with entries in $$S$$ with the property that each $$X_{i,j}$$ has some fixed marginal distribution $$\mathcal{D}$$ on $$S$$ such that $$H$$ has positive probability, and let $$\alpha$$ denote the conditional distribution of $$X_{i,j}$$ obtained by conditioning on $$X_{i,j}\in H$$ (which is well-defined since $$H$$ has positive probability). Moreover, suppose that the entries of the matrix are jointly independent across rows (but the entries within a row need not be independent). An $$H$$-perfect matching of $$X$$ (Def. 5) is a bijection $$\sigma:[n]\to [n]$$ such that $$X_{i,\sigma(i)}\in H$$ for all $$i\in [n]$$. Let $$M(X)$$ denote the (random, possibly empty) set of $$H$$-perfect matchings of $$X$$.

Theorem 1 appears to claim that, under just these assumptions, conditioned on $$X$$ having a $$H$$-perfect matching, the distribution of $$(X_{1,\tau(1)},\ldots,X_{n,\tau(n)})$$ factorizes as a product measure over $$\alpha$$, where $$\tau$$ is chosen uniformly at random among all $$H$$-perfect matchings of $$X$$. That is, for any $$(x_1,\ldots,x_n)\in H^n$$, $$\begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=x_i,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\prod_{i=1}^n \alpha(x_i), \end{equation*}$$ where $$\mathsf{U}[M(X)]$$ is the uniform distribution over $$H$$-perfect matchings in $$X$$.

For a counterexample, just take Peres' example verbatim. Let $$S=\{1,2,3\}$$ and $$H=\{1,2\}$$. For each row of $$X$$ independently, with probability $$1/2$$, sample the entries of the row i.i.d. uniformly $$1$$ or $$2$$, and with probability $$1/2$$, sample the entries of the row i.i.d. uniformly $$1$$ or $$3$$. Call the first situation $$A$$ and the second situation $$B$$. The marginal law of each $$X_{i,j}$$ is clearly $$1$$ with probability $$1/2$$ and $$2$$ or $$3$$ with probability $$1/4$$ each. The conditional law $$\alpha$$ of $$X_{i,j}$$ given $$X_{i,j}\in H$$ is $$X_{i,j}=1$$ with probability $$2/3$$ and $$X_{i,j}=2$$ with probability $$1/3$$.

Let's compute $$\begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right). \end{equation*}$$ Theorem 1 appears to claim that this should be $$\alpha(2)^n=(1/3)^n$$.

It's easy to see that that the probability $$M(X)\neq \emptyset$$ is $$1-o(1)$$ by comparison with the probability that a random bipartite graph with $$1/2$$ edge probability has a perfect matching via the obvious coupling. Now, we have $$\begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via A}\bigg\vert M(X)\neq \emptyset\right). \end{equation*}$$ This holds simply because if all entries in any perfect matching are $$2$$, all rows must have been sampled according to situation $$A$$. We thus have $$\begin{equation*} \Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\,\land\, \text{all rows sampled via A}\bigg\vert M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via A}\,\land\,M(X)\neq \emptyset\right)\cdot\Pr\left(\text{all rows sampled via A}\vert M(X)\neq \emptyset\right). \end{equation*}$$ For the second factor, by Bayes' rule, we have $$\begin{equation*} \Pr\left(\text{all rows sampled via A}\vert M(X)\neq \emptyset\right)= \frac{\Pr\left(\text{all rows sampled via A}\right)}{\Pr(M(X)\neq \emptyset)}=\frac{1+o(1)}{2^n}, \end{equation*}$$ since the event that all rows are sampled via $$A$$ implies there exists a $$H$$-perfect matching. For the first factor, note that $$\begin{equation*} \Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via A}\,\land\,M(X)\neq \emptyset\right)=\Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via A}\right), \end{equation*}$$ since again, the event that all rows are sampled via $$A$$ implies the existence of $$H$$-perfect matchings. In fact, all perfect matchings are valid if $$A$$ occurs since necessarily every entry is in $$H$$ by construction. But given $$A$$ occurs for every row, the joint law of all entries of the matrix is i.i.d. uniform over $$1$$ or $$2$$, independent of the choice of uniform random matching. So we have $$\begin{equation*} \Pr_{\tau\sim U[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert \text{all rows sampled via A}\right)=\frac{1}{2^n}. \end{equation*}$$ Putting it together, we find that $$\Pr_{\tau\sim \mathsf{U}[M(X)]}\left(X_{i,\tau(i)}=2,\forall i\in [n]\bigg\vert M(X)\neq \emptyset\right)=\frac{1+o(1)}{4^n}\ll \frac{1}{3^n}$$.

• Thank you; I shall accept this answer once I’ve read it more closely. Jan 1 at 16:03