The powers-of-three complexity conjecture

Let O={1,S,+,}O=\{1,S,+,*\} and O={1,S,+,}O_{|}=\{1,S,+,*\} denote the two operation sets considered, and let cO(n)c_O(n) and cO(n)c_{O_{|}}(n) be their corresponding complexities.

Powers-of-three complexity conjecture. For every kNk\in\mathbb N,

cO(3k)=4k1.c_O(3^k)=4k-1.

Alternatively, for every kNk\in\mathbb N,

cO(2k)=2k.c_{O_{|}}(2^k)=2k.

The source immediately notes that the lower-bound result implies this conjecture cannot hold simultaneously with the asymptotic complexity conjecture; accordingly, this candidate is refuted.

Sources & referencesView supporting material

Primary source

Akshunna Shaurya Dogra, “Optimal Presentations of Mathematical Objects”, arXiv:1812.00972 (2018).

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.