Asymptotic gap between monotone and non-monotone formula complexity

About 8 years old · traced to

Let a0=2−1a_0=2-1 and, for n≥0n\geq 0, let

an+1=21+an−1.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~(an−1)\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.

References

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.