9
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – palindrome
    Sep 22 '15 at 4:04
  • 1
    $\begingroup$ Calabro, Impagliazzo, and Paturi define the SETH explicitly with respect to randomised algorithms. Your statement for the ETH is also incompletely specified and misleading. $\endgroup$
    – András Salamon
    Sep 24 '15 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.