Izaak Meckler

Quadratic proof-complexity lower bounds from large scale geometry

Posted on February 28, 2017
\(\newcommand{\Set}[1]{\left\{#1\right\}}\) \(\newcommand{\angled}[1]{\langle #1 \rangle}\) \(\newcommand{\what}{\widehat}\) \(\newcommand{\bz}{\mathbb{Z}}\) \(\newcommand{\bn}{\mathbb{N}}\)

Today I want to talk about a quadratic proof complexity lower bound for a certain coNP complete problem (in a certain proof system). The most interesting thing about this lower bound is that it comes from a simple application of theorems from large scale geometry/geometric group theory, and so further demonstrates the utility of the large-scale-geometric point-of-view for thinking about computational complexity. (I've written previously about such an application here.)

The coNP complete problem will be the word problem for reversible circuits. Let's say again what that is. There is a certain subgroup \(G\) of the group of permutations of bi-infinite bitstrings \(S(2^\bz)\). It is generated by the following elements:

  • \(\sigma\), a shift:
  • For each of the \(2^3!\) possible 3-bit reversible gates, \(g\), the map \(\what{g}\) which applies this gate to the first three bits:

The word problem for \(G\) is coNP hard since reversible circuits can be encoded as elements of the group. Given a reversible circuit \(C\), let \(|C|\) denote the length of the word representing \(C\) via this encoding.

Via this encoding, we can prove the following lower bound:

Theorem: Suppose we have a finite collection of rewrite rules \[p_i \to q_i\] where \(p_i\) and \(q_i\) are reversible circuits which compute the same function and such that if \(C\) computes the identity function then there exists a sequence of rewrites of length at most \(L(|C|)\) rewriting \(C\) to the empty string.

Then for some constant \(c\), \(L(n) \geq c n^2\) infinitely often.

Proof. Suppose we had such a set of rewrite rules \(\Set{p_i \to q_i : i \in I}\). Consider the set of relations \(R = \Set{ p_i q_i^{-1} : i \in I}\). I claim that \(\angled{\sigma, \what{g_1}, \dots, \what{g_{2^3!}} | R}\) is a presentation for \(G\) (where \(g_1, \dots, g_{2^3}!\) are the \(2^3!\) possible gates on \(3\) bits).

First, this group surjects onto \(G\) via the map \(\varphi\) which sends each generator to the corresponding generator in \(G\): every relation \(p_i q_i^{-1}\) holds in \(G\) since \(p_i\) and \(q_i\) compute the same functions (which means they are equal as elements in \(G\)). Second, this map is injective. If \(w \in \ker H\), then \(w\) is a circuit representing the identity function, which by assumption there is a sequence of rewrites taking \(w\) to the empty string. Each of these rewrites \(p_i \to q_i\) corresponds to an equality which holds in \(H\) (since \(p_i =_H q_i\)). Thus we have \(w =_H e\), the identity, so \(\ker H\) is trivial.

So \(\angled{\sigma, \what{g_1}, \dots, \what{g_{2^3!}} | R}\) is a presentation for \(G\). Moreover, since every sequence of rewrites taking a trivial word \(C\) to the identity has length at most \(L(|C|)\), the Dehn function for \(G\) with this presentation is at most \(L(n)\). Suppose for every constant \(c\), \(L(n) < c n^2\) eventually. Then, by the isoperimetric gap theorem, \(G\) satisfies a linear isoperimetric inequality.

But then, (see Theorem 3.22 here), \(G\) must be hyperbolic. However, this is a contradiction. To show \(G\) is not hyperbolic, it suffices to exhibit an infinite torsion subgroup. That is, an infinite subgroup \(H \leq G\) such that for every \(h \in H\), \(h^k = e\) for some \(k\) (where \(e \in G\) is the identity). Let \(g \in G\) be negation on the \(0\)th bit. I.e., \[ g(w) = i \mapsto \begin{cases} \neg g(i) & i = 0 \\ g(i) & \text{otherwise} \end{cases} \] Clearly \(g^2 = e\). Now consider \(g_k := \sigma^{-k} g \sigma^k\) for \(k \in \bn\). This is negation on the \(k\)th bit. Let \(H = \angled{g_k : k \in \bn}\). \(H\) is infinite, and every \(g_k\) has order two. And each pair \(g_{k_1}, g_{k_2}\) commute (if you negate bit \(k_1\) then bit \(k_2\), it is the same as negating bit \(k_2\) and then bit \(k_1\)). Thus, \(H\) is none other than \(\oplus_{k \in \bn} \mathbb{Z}_2\), an infinite direct sum of \(\mathbb{Z}_2\)s. So, \(H\) is an infinite torsion subgroup, which means \(G\) cannot be hyperbolic.

Take aways

At this point, we've shown that any system of "rewrite rules" for discovering triviality of circuits will take at least quadratically many rewrites on some trivial circuit. The proof uses the large scale geometry of a group \(G\) of reversible circuits. Roughly the only part that used the fact that \(G\) was a group was for certifying non-hyperbolicity via the existence of an infinite torsion subgroup. This suggests that it may be possible to extend this argument to non-reversible circuits by constructing a space of circuits whose non-hyperbolicity could be verified by some other means.