# Exponential time hypothesis for random algorithms

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?

• You might want to check out arxiv.org/pdf/1206.1775v1.pdf It introduces a number of related conjectures to the ETH, including a randomized version. – palindrome Sep 22 '15 at 4:04
• 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 Sep 24 '15 at 8:10