Asymptotic gap between monotone and non-monotone formula complexity

Let a0=21a_0=2-1 and, for n0n\geq 0, let

an+1=21+an1.a_{n+1}=2^{1+a_n}-1.

Consider formula encodings whose gates are restricted to \{+,\times,\text{^}\} and whose inputs are restricted to {1,1}\{-1,1\}. The asymptotic-gap conjecture. The gap between the monotone and non-monotone complexity of the positive integer ana_n is O~(an1)\widetilde{O}(a_{n-1}), allowing for poly-logarithmic factors. The conjecture concerns the potential size reduction obtained by using non-monotone formula encodings instead of monotone ones in this restricted arithmetic setting.

Sources & referencesView supporting material

Primary source

Edinah K. Gnang and Jeanine S. Gnang, “Sketch for a Theory of Constructs”, arXiv:1808.03743 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.