Asymptotic gap between monotone and non-monotone formula complexity
Asymptotic gap between monotone and non-monotone formula complexity
Let and, for , let
Consider formula encodings whose gates are restricted to \{+,\times,\text{^}\} and whose inputs are restricted to . The asymptotic-gap conjecture. The gap between the monotone and non-monotone complexity of the positive integer is , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.