Questions tagged [probabilistic-algorithms]
Questions about (typically randomized) algorithms that can produce no or an incorrect answer with a certain probability.
202
questions
3
votes
1
answer
133
views
Randomized String Searching
I need to detect whether a binary pattern $P$ of length $m$ occurs in a binary text $T$ of length $n$ where $m < n$.
I want to state an algorithm that runs in time $O(n)$ where we assume that ...
- 641
4
votes
2
answers
244
views
Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?
I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?
Clarification:
Note that since the execution of the machine is not deterministic, ...
- 21.9k