<p>The exponential time hypothesis asserts that an algorithm for SAT must take time $2^{\Omega(n)}$. If I am reading this right, this refers only to deterministic algorithms. </p>

<p>Is it possible that ETH holds, yet their is a random algorithm in time $2^{o(n)}$? If so, is there any name for the hypothesis that any randomized (say BPP-type) algorithm takes time $2^{\Omega(n)}$ as well? </p>

CC BY-SA 3.0
2015-09-22T04:04:11.967Z
You might want to check out http://arxiv.org/pdf/1206.1775v1.pdf
It introduces a number of related conjectures to the ETH, including a randomized version.
palindrome
CC BY-SA 3.0
2015-09-24T08:10:57.037Z
Calabro, Impagliazzo, and Paturi define the SETH explicitly with respect to randomised algorithms.  Your statement for the ETH is also incompletely specified and misleading.
András Salamon
<cc.complexity-theory><randomized-algorithms>
Exponential time hypothesis for random algorithms
David Harris
# Exponential time hypothesis for random algorithms

(Asked by: username_0 on 2015-09-21)

The exponential time hypothesis asserts that an algorithm for SAT must take time $2^{\Omega(n)}$. If I am reading this right, this refers only to deterministic algorithms.

Is it possible that ETH holds, yet their is a random algorithm in time $2^{o(n)}$? If so, is there any name for the hypothesis that any randomized (say BPP-type) algorithm takes time $2^{\Omega(n)}$ as well?

**Tags:** cc.complexity-theory, randomized-algorithms

> **Comments:**
> **username_1**: You might want to check out http://arxiv.org/pdf/1206.1775v1.pdf It introduces a number of related conjectures to the ETH, including a randomized version.  
> **username_2**: Calabro, Impagliazzo, and Paturi define the SETH explicitly with respect to randomised algorithms.  Your statement for the ETH is also incompletely specified and misleading.  

---

## 0 answers

