The powers-of-three complexity conjecture
The powers-of-three complexity conjecture
Let and denote the two operation sets considered, and let and be their corresponding complexities.
Powers-of-three complexity conjecture. For every ,
Alternatively, for every ,
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
Sign in to submit a solution.
No solutions have been posted yet.