De um algoritmo randomizado com tempo esperado $ O (n) $ a um confiável com o tempo de execução determinado

Question

Deixe $ a $ ser um algoritmo randomizado e $ F $ ser uma função tal que $ a $ retorna $ f (x) $ em qualquer entrada $ x $ . Além disso, suponha que, para entrada $ x $ de tamanho $ n $ , a matemática $ \ textbf {esperado} $ tempo de execução de $ a $ é $ o (n ) $ . Dê um algoritmo que é garantido para terminar no tempo $ o (n) $ para cada entrada, e que na entrada $ x $ saídas $ f (x) $ com probabilidade pelo menos $ 1- \ VAREPSILON $ e caso contrário retorna $ {\ tt timeout} $ .

Existe uma maneira de fazê-lo com de alguma forma derandando $ a $ e usando a possibilidade de tempo limite de uma maneira inteligente? Eu não tenho outras idéias. Qualquer ajuda apreciada!

Answer 1

escrever $ t_x $ para a variável aleatória representando o tempo de execução da $ a $ na entrada < Classe Span="Recipiente de Matemática"> $ x $ . Pela desigualdade de Markov,

$$ \ PR (t_x \ geq 2 \ operatorName {e} (t_x) \ leq \ frac {1} {2}. $$ .

veja se você pode descobrir uma solução agora.

Solução:

Escolha $ n $ para que $ 2 ^ {- n} <\ varepsilon $ . Para $ 1..n $ , repita o seguinte: Simular $ a (x) $ para $ 2 \ operatorName {e} (t_x) $ etapas com bits aleatórios independentes frescos; Se um valor for retornado dessa simulação, retorne isso imediatamente. Se chegarmos ao final do loop e nenhum dos $ n $ simulações retornaram um valor e, em seguida, retornar tempo limite.