Introduction

Recently, the Computational No-Coincidende Conjecture^[1] was proposed, presented as an assumption that might be needed to develop methods to explain neural nets in the current approach from the Alignment Research Center. In this post, I will prove that some plausible extra assumption can be used to amplify the conjecture, showing it implies an arbitrarily stronger version of itself.

In a slightly weakened version, the conjecture reads:
(weak) Computational no-coincidence conjecture: For a reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$, let $P\left(C\right)$ be the property that there is no input $x$ to $C$ that ends in $n$ zeros, such that $C\left(x\right)$ also ends in $n$ zeros. There exists a polynomial-time verification algorithm $V$ that receives as input:

• A reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$
• An advice string $\pi$

such that:

• For all $C$ such that $P\left(C\right)$ is true, there exists $\pi$ with length polynomial in the size of $C$, such that $V(C,\pi )=1$.
• For 99% of random reversible circuits $C$ for which P(C) is false, no such $\pi$ exists.

The original conjecture omits "for which $P\left(C\right)$ is false". As such $\pi$ always exists when $P\left(C\right)$ is true, the original conjecture implies this weak version.

With an additional assumption, I will show that this (weak) conjecture implies a stronger version of itself, in which the "99%" can be replaced by "$1-ϵ$" for an arbitrarily small $ϵ>0$. This entails the original conjecture can also be strengthened. 

The strategy will be to define a new problem in NP using the conjecture. This problem is to decide whether a reversible circuit is in the set containing all circuits satisfying the property $P$ plus a fraction of those falsifying it. If that fraction is smaller than 1%, we will have an stronger weak conjecture with a probability bound higher than "99%". Iterating this amplification step, that bound will be replaced by "$1-ϵ$", arbitrarily close to one^[2]. To achieve that, we will employ an extra assumption. Then we will apply the results to the original conjecture and discuss how reasonable the extra premise is.

The Amplification Step

Let $C$ be the set of all reversible circuits and let $P⊊C$ denote the set of circuits $C$ such that $P\left(C\right)$ is true. As the authors note, deciding $P$^[3] is coNP-hard, and thus, coNP-complete^[4], implying $\overline{P}$ (the complement of $P$ relative to $C$) is NP-complete.

We assume the (weak) conjecture is true, so there is a polynomial-time verifier $V_0$ such that: for all $C\in P$, there is a polynomial-sized $\pi$ with $V_0(C,\pi )=1$;  and for 99% of random circuits $C\in \overline{P}$, no such $\pi$ exists. Let $V_0$^[5] denote also the set of circuits $C$ (a property) such that there is a $\pi$ yielding $V_0(C,\pi )=1$. By definition, $V_0$ is in NP, implying $\overline{V_0}$ is in coNP. Note that $\overline{V_0}\subseteq \overline{P}$.

Define the set $V_0^{\prime }=V_0\cap \overline{P}$. That is, $V_0^{\prime }$ contains the circuits $C\in C$ such that $P\left(C\right)$ does not hold and there is a $\pi$ with $V_0(C,\pi )=1$. Since both $\overline{P}$ and $V_0$ are in NP, so is $V_0^{\prime }$, and $\overline{V_0^{\prime }}$ is in coNP. Note that $V_0^{\prime }⊊\overline{P}$, and the conjecture implies $Prob\left(V_0\right(C\left)|\overline{P}\right(C\left)\right)=Prob\left(V_0^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}$, for a random $C\in C$ ^[6].

As $V_0^{\prime }$ is in NP, it can be reduced in polynomial time to $\overline{P}$, which is NP-complete. Formally, there is a polynomial-time algorithm $f_0$ (a many-one reduction) such that $C\in V_0^{\prime }$ iff $f_0\left(C\right)\in \overline{P}$. Given such a reduction $f_0$, define the set $V_0^{f_0}=\{C\in C\mid f_0(C)\in V_0\}$. For any $C\in \overline{V_0^{\prime }}$,  $f_0\left(C\right)\in P$ and, by the conjecture, there is a polynomial-sized $\pi$ yielding $V_0\left(f_0\right(C),\pi )=1$, and thus $f_0\left(C\right)\in V_0$ . Therefore, $C\in \overline{V_0^{\prime }}$ implies $C\in V_0^{f_0}$.  Note that $V_0^{f_0}$ is in NP by definition, as we can define a polynomial verification algorithm $V_0^{f_0}(C,\pi )=V_0\left(f_0\right(C),\pi )$ such that $C\in V_0^{f_0}$ iff there is a (polynomial-sized) $\pi$ yielding $V_0^{f_0}(C,\pi )=1$. Also note that  $\overline{V_0^{f_0}}\subseteq V_0^{\prime }$.

Since $V_0$ and $V_0^{f_0}$ are in NP, so is $V_1=V_0\cap V_0^{f_0}$ (the problem we are interested in). This implies there is a polynomial-time verifier $V_1(\cdot ,\cdot )$ such that for any circuit $C\in V_1$, there is a polynomial-sized $\pi$ yielding $V_1(C,\pi )=1$. In particular, for all $C$ satisfying $P$, since $P\subseteq V_1$, and all $C\in V_1\cap \overline{P}$, there is such a $\pi$.

Now define the set of circuits $V_1^{\prime }=V_1\cap \overline{P}=V_0^{\prime }\cap V_0^{f_0}$. As $V_1$ and $\overline{P}$ are in NP, so is $V_1^{\prime }$. The set $V_1^{\prime }$ contains all circuits falsifying $P$ that exhibit a special structure of those circuits satisfying $P$ (there is a $\pi$ with $V_1(C,\pi )=1$). As $V_1^{\prime }\subseteq V_0^{\prime }$, $Prob\left(V_1\right(C\left)|\overline{P}\right(C\left)\right)=Prob\left(V_1^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)$ is not higher than $Prob\left(V_0^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)$, and $V_1(\cdot ,\cdot )$ is a polynomial-time verifier satisfying both conditions in the weak conjecture. For $V_1(\cdot ,\cdot )$ to satisfy a stronger version of the conjecture, with $Prob\left(V_1^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)<Prob\left(V_0^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}$, we need some extra assumption.

The Extra Assumption

 Since $V_1^{\prime }=V_1\cap \overline{P}\subseteq V_0^{\prime }\subseteq \overline{P}$, it follows that, for a random $C\in C$,$Prob\left(V_1^{\prime }\right(C)\mid \overline{P}(C\left)\right)=Prob\left(V_1^{\prime }\right(C)\mid V_0^{\prime }(C\left)\right)Prob\left(V_0^{\prime }\right(C)\mid \overline{P}(C\left)\right)$. So we just need an assumption yielding $Prob(C\in V_1^{\prime }|C\in V_0^{\prime })=Prob\left(f_0\right(C)\in V_0^{\prime }\mid C\in V_0^{\prime })<1$ in order for the polynomial verifier $V_1$ to satisfy a stronger version of the weak conjecture.

Recall that $C\in V_0^{\prime }$ iff $f_0\left(C\right)\in \overline{P}$, and note that $Prob(C\in V_1|C\in V_0^{\prime })$ is equal to $Prob\left(f_0\right(C)\in V_0|C\in V_0^{\prime })=Prob\left(f_0\right(C)\in V_0^{\prime }|C\in V_0^{\prime })$. Thus we need an assumption entailing $Prob\left(f_0\right(C)\in V_0^{\prime }\mid f_0(C)\in \overline{P})<1$, or, equivalently, $Prob\left(f_0\right(C)\in \overline{V_0^{\prime }}\mid f_0(C)\in \overline{P})>0$. This inequality says that, given a random reversible circuit $C$ for which $P\left(f_0\right(C\left)\right)$ is false, $f_0\left(C\right)$ has non-zero probability of being in $\overline{V_0}$ (not having a $\pi$ such that $V_0\left(f_0\right(C),\pi )=1$). For a random $C$ falsifying $P$, the conjecture implies $Prob(C\in \overline{V_0^{\prime }}\mid C\in \overline{P})\ge 99$%,  thus we might wonder whether this probability bound is robust to applying a reduction to $C$. Nonetheless, by employing an arbitrary number of iterations of the amplification step, as we will show, we can achieve the desired strengthening of the conjecture with a much weaker premise^[7]: 

Reduction-Regularity:^[8] There is a $\delta \in (0,1)$ such that, given any NP problem $L⊊\overline{P}$ with $Prob(C\in \overline{L}\mid C\in \overline{P})\ge 99\%$ for a random $C\in C$, there is a polynomial-time reduction $f(.)$ from $L$ to $\overline{P}$ yielding $Prob\left(f\right(C)\in \overline{L}\mid f(C)\in \overline{P})\ge \delta$ for a random $C$.

While the (weak) conjecture implies $Prob\left(V_0^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}$, for a random $C\in C$, assuming also the premise above (with $L=V_0^{\prime }$) implies there is a reduction $f_0$ such that $Prob\left(V_1^{\prime }\right(C\left)|V_0^{\prime }\right(C\left)\right)\le 1-\delta$.  Consequently, we obtain $Prob\left(V_1^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)=Prob\left(V_1^{\prime }\right(C\left)|V_0^{\prime }\right(C\left)\right)Prob\left(V_0^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}(1-\delta )$. This seems a small gain, as $\delta$ can be close to zero, but it is sufficient to iteratively amplify the weak conjecture.

Amplifying the Weak Conjecture

The whole process can be repeated to achieve a higher probability bound. The weak conjecture and Reduction-Regularity imply $Prob\left(V_1\right(C\left)|\overline{P}\right(C\left)\right)\ge 0.99+{10}^{-2}\delta$, which would already give us a stronger version of the weak conjecture. But now Reduction-Regularity (with $L=V_1^{\prime }$) implies there is a polynomial many-one reduction $f_1$ from $V_1^{\prime }=V_1\cap \overline{P}$ to $\overline{P}$ such that $Prob\left(f_1\right(C)\notin V_1^{\prime }|f_1(C)\in \overline{P})\ge \delta$. Defining  $V_2=V_1\cap V_1^{f1}$, where $V_1^{f_1}=\{C\in C|f_1(C)\in V_1\}$, and $V_2^{\prime }=V_2\cap \overline{P}$, this entails $Prob\left(\overline{V_2}\right(C\left)|V_1^{\prime }\right(C\left)\right)\ge \delta$ and $Prob\left(V_2\right(C\left)|V_1^{\prime }\right(C\left)\right)=Prob\left(V_2^{\prime }\right(C\left)|V_1^{\prime }\right(C\left)\right)\le 1-\delta$. As $Prob\left(V_1^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}(1-\delta )$ and  $V_2^{\prime }\subseteq V_1^{\prime }\subseteq \overline{P}$, it follows that:

$Prob\left(V_2\right(C\left)|\overline{P}\right(C\left)\right)=Prob\left(V_2^{\prime }\right(C\left)|V_1^{\prime }\right(C\left)\right)Prob\left(V_1^{\prime }\right(C\left)|\overline{P}\right(C\left)\right)\le {10}^{-2}(1-\delta {)}^2$ 

Note that $P\subseteq V_2$, so $V_2$ would satisfy an even stronger conjecture. 

The amplification step can be iterated inductively. For any positive $i\in N$, given $V_i^{\prime }$ is in NP, we can construct a reduction $f_i$ from $V_i^{\prime }$ to $\overline{P}$ (via Reduction-Regularity) such that defining $V_{i+1}=V_i\cap V_i^{f_i}$ and $V_{i+1}^{\prime }=V_{i+1}\cap \overline{P}$ yields $Prob\left(\overline{V_{i+1}^{\prime }}\right(C\left)|V_i^{\prime }\right(C\left)\right)\ge \delta$ and $Prob\left(V_{i+1}^{\prime }\right(C\left)|V_i^{\prime }\right(C\left)\right)=Prob\left(V_{i+1}\right(C\left)|V_i^{\prime }\right(C\left)\right)\le 1-\delta$. If the amplification is iterated $m$ times, we have:

$Prob\left(V_m\right(C\left)|\overline{P}\right(C\left)\right)=Prob\left(V_0\right(C\left)|\overline{P}\right(C\left)\right)\prod _{i=1}^{m}Prob\left(V_i\right(C\left)|V_{i-1}^{\prime }\right(C\left)\right)\le (1-\delta {)}^m{10}^{-2}$ 

Given any $ϵ\in (0,1)$, we can choose an $m\in N$ such that ${10}^{-2}(1-\delta {)}^m\le ϵ$, or $m\ge {\log }_{1-\delta }\left({10}^2ϵ\right)$.   Iterating the amplification step $m$ times thus yields $Prob\left(V_m\right(C\left)|\overline{P}\right(C\left)\right)\le ϵ$ and, consequently, $Prob\left(\overline{V_m}\right(C\left)|\overline{P}\right(C\left)\right)\ge 1-ϵ$. Note that $V_m$ is exactly the set of reversible circuits $C$ for which there is a $\pi$ yielding $V_m(C,\pi )=1$, for a polynomial verifier $V_m(\cdot ,\cdot )$, since $V_m$ is in NP. Furthermore, $P\subseteq V_m.$ Therefore the (weak) conjecture, together with Reduction-Regularity, implies:

Amplified (weak) Computational no-coincidence conjecture: For a reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$, let $P\left(C\right)$ be the property that there is no input $x$ to $C$ that ends in $n$ zeros, such that $C\left(x\right)$ also ends in $n$ zeros. For any $ϵ\in (0,1)$, there exists a polynomial-time verification algorithm $V$ that receives as input:

• A reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$
• An advice string $\pi$

such that:

• For all $C$ such that $P\left(C\right)$ is true, there exists $\pi$ with length polynomial in the size of $C$, such that $V(C,\pi )=1$.
• For $100(1-ϵ)$% of random reversible circuits $C$ for which P(C) is false, no such $\pi$ exists.

Note that, relative to the size of the circuit $C$, the algorithm $V$ (or $V_m$) still runs in polynomial time and $\pi$ still is polynomial-sized. Nonetheless, the number $m$ of amplification iterations needed for a given $ϵ$ is proportional to $\log 1/ϵ$ if we assume a fixed $\delta \in (0,1)$. This implies the computational complexity of $V$ and $\pi$ might increase exponentially on $1/ϵ$, as indicated in the Appendix. 

Amplifying the Original Conjecture

The amplified weak conjecture can finally be used to amplify the original one. Let $\alpha \in (0,1)$ be such that $Prob(C\in P)=\alpha$ and $Prob(C\in \overline{P})=1-\alpha$. Since $Prob\left(\overline{V}\right(C\left)|P\right(C\left)\right)=0$ for any $V$ satisfying the amplified weak conjecture, the latter implies that, for any $ϵ\in (0,1)$, there is a $V$ such that $Prob\left(\overline{V}\right(C\left)\right)=Prob\left(\overline{P}\right(C\left)\right)Prob\left(\right(\overline{V}\left(C\right)|\overline{P}\left(C\right))\ge (1-\alpha \left)\right(1-ϵ)$. Note that $Prob\left(\overline{V}\right(C\left)\right)\le 1-\alpha$, for all $C\in P$ is also in $V$, as required by the amplified conjecture. Hence, we can make the probability bound arbitrarily close to that limit, and, assuming Reduction-Regularity, the (weak) conjecture implies:

Amplified Computational no-coincidence conjecture: For a reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$, let $P\left(C\right)$ be the property that there is no input $x$ to $C$ that ends in $n$ zeros, such that $C\left(x\right)$ also ends in $n$ zeros. Let $\alpha \in (0,1)$ be such that exactly $100\alpha \%$ of  random reversible circuits satisfy P. For any $ϵ\in (0,1)$, there exists a polynomial-time verification algorithm $V$ that receives as input:

• A reversible circuit $C:\{0,1{\}}^{3n}\to \{0,1{\}}^{3n}$
• An advice string $\pi$

such that:

• For all $C$ such that $P\left(C\right)$ is true, there exists $\pi$ with length polynomial in the size of $C$, such that $V(C,\pi )=1$.
• For $100(1-ϵ)(1-\alpha )\%$ of random reversible circuits $C$, no such $\pi$ exists.

The Reasonability of Reduction-Regularity

Before speculating about the implications of these results, we have to check how reasonable Reduction-Regularity is. At first, it might appear that it is just a harmless assumption. Upon closer look, we can see, for instance, that it implies a $\delta$-fraction of the circuits in $V_i^{\prime }$ to be reduced (via $f_i$) to circuits in $\overline{P}\setminus V_i^{\prime }$. All circuits in $V_i^{\prime }\subset V_i$ show the special structure ($V_i(C,\pi )=1$) without satisfying the property $P$. Therefore, it is plausible to conceive that $C\in V_i^{\prime }$ might imply probability 100% for $f_i\left(C\right)\in V_i^{\prime }\subset V_i$, even though at least 99% of the circuits in $\overline{P}$ are not in $V_i\subseteq V_0$. Against that, we can argue that $f_i$ can be constructed as a composition of reductions, for instance reducing $V_i^{\prime }$ to SAT and then reducing SAT to $\overline{P}$, probably washing away any possible structure that entail $f_i\left(C\right)\in V_i^{\prime }$(C). In the end, the plausibility of Reduction-Regularity might depend on the specific probability distribution over circuits; personally, I believe this premise is quite reasonable, and maybe it can be supported by some empirical experiments.

Reduction-Regularity can actually be weakened, as we just need an infinite number of i's such that $Prob\left(V_i\right(C\left)|V_{i-1}^{\prime }\right)\le 1-\delta$. Let $I\subseteq N$ be the (infinite) set of such values of $i$, with $I=\{i_1,i_2,i_3\dots \}$ such that $i_1<i_2<i_3\dots$. Then the $m$ amplification iterations with the original Reduction-Regularity can be emulated with $i_m$ iterations using this weakened version. Though the bounds derived in the Appendix do not hold anymore, intuitively the weakened version should be even more plausible. 

Conclusion

Assuming Reduction-Regularity, we might speculate whether the original conjecture is likely by analysing its amplified version. Intuitively, the strengthened version should decrease our credence on the conjecture, but it is not clear to what amount. It is tempting to consider what happens when $m$ tends to infinity, as $ϵ$ tends to zero and $V_i^{\prime }$tends to the empty set. This would imply $P\cup V_i^{\prime }=P$ is in NP, but we know it is coNP-hard, so we would have NP=coNP. However, the running time of the verifier might increase exponentially on $1/ϵ$, as indicated in the Appendix, or the complexity of $f_i$ might increase with $i$, not being polynomial in the limit. 

Personally, I am inclined to think the conjecture is false. If the conjecture is indeed false, then it follows that NP$\ne$coNP^[9] and, consequently, P$\ne$NP. Hence, it should be rather hard to prove the conjecture is false.

Appendix

To derive an upper bound for the complexities of $V$ and $\pi$ in the amplified conjecture after $m$ amplification iterations, we construct an algorithm for $V_1(\cdot ,\cdot )$ using $V_0(\cdot ,\cdot )$, $f_0$ and $V_0^{f_0}(\cdot ,\cdot )$. Recall that $V_1(\cdot ,\cdot )$ is a verifier for $V_0\cap V_0^{f_0}$, $V_0(\cdot ,\cdot )$ is a verifier for $V_0$ and $V_0^{f_0}(\cdot ,\cdot )$ is a verifier for $V_0^{f_0}$. To verify that $C\in V_0\cap V_0^{f_0}$, we can verify that $C\in V_0$ and $C\in V_0^{f_0}$. $C\in V_0$ iff there is a ${\pi }_0$ such that $V_0(C,{\pi }_0)=1$; $C\in V_0^{f_0}$ iff there is a ${\pi }_{f_0}$ such that  $V_0^{f_0}(C,{\pi }_{f_0})=V_0\left(f_0\right(C),{\pi }_{f_0})=1$. Hence, $V_1(\cdot ,\cdot )$ can be defined via the multiplication $V_1(C,{\pi }_0{\pi }_{f_0})=V_0(C,{\pi }_0)V_0\left(f_0\right(C),{\pi }_{f_0})$,^[10] such that $C\in V_1$ iff there are ${\pi }_0$ and ${\pi }_{f_0}$ such that $V_1(C,{\pi }_0{\pi }_{f_0})=1$. The complexity of $V_1(\cdot ,\cdot )$ is thus dominated by the complexity of $V_0^{f_0}(\cdot ,\cdot )$. Assuming $|{\pi }_0|\in O\left(|C{|}^{\alpha }\right)$ and the time to run $V_0(C,\pi )$ is $O\left(\right(|C|+|\pi |{)}^{\beta })$, it follows that $V_0$ is in $O\left(\right(|C{|}^{\alpha \beta })$.  If the time to run $f_0\left(C\right)$ is $O\left(|C{|}^{\gamma }\right)$, then the time to run $V_1(C,\pi )=V_0\left(f_0\right(C),\pi )$ is  $O\left(\right(|C{|}^{\alpha \beta \gamma })$ and the size of its certificate is $O\left(|C{|}^{\alpha \gamma }\right)$. That is, after one iteration of the amplifying step, the size of the certificate $\pi$ and the and the run time of the verifier have their upper bound raised to the power of $\gamma$. After $m$ iterations, they will be raised to the power of ${\gamma }^m$ (assuming all $f_i$ have the same complexity^[11]), hence increasing doubly exponentially on $m$, unless $\gamma =1$ (all reductions run in linear time). Since $m=O\left(\log 1/ϵ\right)$ for a fixed $\delta$, both complexity bounds would increase exponentially on $1/ϵ$. 

1. ^{^}

   Also posted at LessWrong.

2. ^{^}

   In the original conjecture, this probability cannot arbitrarily approach 1, as there is a positive probability for $P\left(C\right)$ being true, as we will discuss.

3. ^{^}

   We use the same symbol, say $S$, to denote a property of circuits, the set of circuits satifying that property and the problem of deciding, given a circuit $C\in C$, whether $C\in S$ (or, equivalently, $S\left(C\right)$).

4. ^{^}

   To verify that a $C$ is in $\overline{P}$, one can guess an input that ends with $n$ zeros and obtain the output ending with zeros in polynomial time. Thus $\overline{P}$ is in NP and $P$ is in coNP. 

5. ^{^}

   Abusing the notation, we use the same symbol for a set in NP and the corresponding polynomial-time verifier.

6. ^{^}

   We think the probability distribution should not matter, as the conjecture's authors write, but they show a possible distribution to be concrete. 

7. ^{^}

   This premise can be weakened as we discuss later.

8. ^{^}

   This is admittedly not a good name, and suggestions are welcome.

9. ^{^}

   If NP=coNP, then deciding the property $P$ is in NP, and there is a verifier satisfying the conjecture.  

10. ^{^}

    For strings $a$ and $b$, $ab$ denotes their concatanation.

11. ^{^}

    This might be a rather strong assumption, as the complexity of $f_i$ might increase with $i$.