5
votes
Is there a problem known to have no fastest algorithm, up to polynomials?
This is essentially true for matrix multiplication, as shown in this paper: https://ieeexplore.ieee.org/document/4568320.
The "essentially" is because what they actually show is that this is ...
- 5,083
2
votes
A potentially novel complexity measure for sets of strings
One possible measure of the "complexity" of a set of strings is the size of the minimal DFA that accepts exactly those strings (and no others). I can't tell whether this has the properties ...
- 12.3k
Only top scored, non community-wiki answers of a minimum length are eligible