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
4
votes
Accepted
Norm in the definition of sampling computational complexity class SampP
They use variation distance (page 8 in the linked paper), which is essentially $L_1$. For two discrete distributions $\|A - B\| = \frac12\sum_{\omega \in \Omega} |A(\omega) - B(\omega)|$.
- 687
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