New answers tagged cc.complexity-theory
-1
votes
Halting problem with minimal Turing Machine as promised input
How about first asking your question for a more powerful machine A*, which is a trial-and-error machine that can change its mind once and does not have to halt. I believe you can show that A* cannot ...
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
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
Top 50 recent answers are included