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}^{3 n} \to {0, 1}^{3 n}$ , let $P (C)$ be the property that there is no input $x$ to $C$ that ends in $n$ zeros, such that $C (x)$ also ends in $n$ zeros. There exists a polynomial-time verification algorithm $V$ that receives as input:

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

such that:

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

The original conjecture omits "for which $P (C)$ is false". As such $π$ always exists when $P (C)$ 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 (C)$ is tr...

Posts

Wikitag Contributions

Comments