Problemas em P com algoritmos aleatoriamente comprovadamente mais rápidos

Existem problemas no que têm algoritmos aleatórios que ultrapassam limites inferiores em algoritmos determinísticos? Mais concretamente, conhecemos algum para o qual ? Aqui significa o conjunto de idiomas decidíveis por uma TM aleatória com erro de limite constante (um ou dois lados) nas etapas . $\mathsf{P}$ $k$ $\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$ $\mathsf{PTIME}(f(n))$ $f(n)$

A aleatoriedade nos compra alguma coisa dentro de $\mathsf{P}$ ?

Para deixar claro, estou procurando algo em que a diferença seja assintótica (de preferência polinomial, mas eu aceitaria a polilogarítmica), não apenas uma constante.

Estou procurando algoritmos assintoticamente melhores no pior dos casos. Algoritmos com maior complexidade esperada não são o que estou procurando. Quero dizer algoritmos aleatórios como em RP ou BPP não ZPP.

algorithms complexity-theory randomized-algorithms aelguindy
fonte

Talvez a "técnica de Yao" seja o que você está procurando. Uma breve descrição pode ser encontrada em cs.pitt.edu/~kirk/cs2150/yao/yao.html

Wu Yin

@WuYin, se eu entendi direito, isso vai na direção de algoritmos aleatórios de limite inferior pelo comportamento médio de caso do algoritmo determinístico. se não nos comprar qualquer coisa dentro .. Estou correto?

P

$P$

aelguindy

Para encontrar qualquer elemento na sequência de comprimento com classificação em [ , ], podemos simplesmente retornar qualquer elemento aleatório e ele estará correto com probabilidade, portanto, é O (1)! Enquanto um algoritmo determinístico examinaria pelo menos alguma fração da entrada e, portanto, .

n

$n$

\frac{n}{4}

$\frac{n}{4}$

\frac{3 * n}{4}

$\frac{3*n}{4}$

\frac{1}{2}

$\frac{1}{2}$

Ω (n)

$\Omega(n)$

rizwanhudda

@rizwanhudda Pode haver alguns problemas com isso. Primeiro, estou procurando um problema de decisão. Segundo, no modelo de Turing, o retorno de um elemento aleatório é , pois não há acesso aleatório. Talvez, a máquina sempre produz o primeiro elemento? Ainda assim, o primeiro problema é maior.

Ω (n)

$\Omega (n)$

aelguindy

O último parágrafo não faz sentido porque todo algoritmo de Las Vegas pode ser convertido em um algoritmo de Monte Carlo.

Tsuyoshi Ito

Respostas:

O teste de identidade polinomial admite um algoritmo de tempo polinomial aleatório (consulte o lema de Schwartz-Zippel ) e, atualmente, não temos um tempo polinomial determinístico ou mesmo um algoritmo de tempo subexponencial para ele.

Avaliação da árvore de jogo Considere uma árvore binária completa com nós de folha, cada um armazenando um valor 0/1. Os nós internos contêm portas OR / AND em níveis alternativos. Pode-se provar, usando o argumento adversário, que todo algoritmo determinístico teria que examinar nós de folha no pior caso. No entanto, existe um algoritmo aleatório simples que levao tempo de execução esperado de Veja os slides 14 a 27 da palestra. $n$ $\Omega{(n)}$ $O(n^{0.793})$

Roteamento inconsciente em um hipercubo Considere um cubo em dimensões contendo vértices. Cada vértice possui um pacote de dados e um destino para o qual deseja entregar o pacote. O destino de todos os pacotes é diferente. Mesmo para isso, ficou provado que qualquer estratégia determinística de roteamento levaria $n$ $N=2^n$ etapas. No entanto, existe uma estratégia aleatória simples que termina emetapasesperadascom alta probabilidade. $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ $O(n)$

Observe que, em algoritmos aleatórios, o custo esperado com alta probabilidade (como por exemplo: $E(F(n))$ ) é equivalente ao pior caso na prática. $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$

rizwanhudda
fonte

Além disso, considerar o teste para as matrizes

. Atualmente, não conhecemos

algoritmo

, conhecemos um algoritmo

randomizado . A questão é: existem problemas para os quais podemos provar que algoritmos aleatórios são melhores?

A

$A$

B

$B$

C

$C$

A B = C

$A B = C$

o (2^{2.3})

$o(2^{2.3})$

O (n^{2})

$O(n^2)$

aelguindy

@aelguindy Eu entendo o seu ponto. Mas, para o PIT, o algoritmo determinístico mais conhecido é exponencial. E, a desarmonização do TPI é um importante problema em aberto no CS teórico.

rizwanhudda

Adicionei avaliação de árvore de jogo e roteamento de hipercubo à publicação, para a qual os algoritmos aleatórios são comprovadamente melhores que os homólogos determinísticos.

Rizwanhudda

OK, para a avaliação da Árvore de Jogos, se bem entendi, ela é executada no

esperado

, certo? Quero dizer, há casos em que ele será executado em

. Também é o caso do terceiro exemplo? Não estou permitindo o melhor tempo esperado, estou procurando uma melhor complexidade do pior caso, erro permitido na saída.

O (n^{0.793})

$O(n^{0.793})$

Ω (n)

$\Omega(n)$

aelguindy

Portanto, eles não são melhores no pior dos casos. Por mais que eu aprecie os exemplos, receio que não seja exatamente o que estou procurando. Os exemplos foram muito esclarecedores!

aelguindy

Investigar o pior caso não faz sentido para algoritmos aleatórios. Não apenas o pior tempo de execução geralmente será infinito, mas também não podem superar os algoritmos determinísticos nessa métrica.

Considere qualquer algoritmo aleatório . Obtenha um algoritmo determinístico fixando a fita aleatória de a . Em seguida, para todos os . $A$ $B$ $A$ $0^\infty$ $T_B(n) \leq T_A(n)$ $n$

Rafael
fonte

Existem muitos problemas nos quais conhecemos um algoritmo aleatório eficiente e não conhecemos nenhum algoritmo determinístico que possamos provar ser eficiente. No entanto, isso pode refletir deficiências em nossa capacidade de provar coisas sobre complexidade em vez de qualquer diferença fundamental.

Com base no seu comentário , parece que você quis perguntar se existe algum problema em que exista um algoritmo aleatório eficiente, e podemos provar que não existe um algoritmo determinístico de eficiência comparável. Não conheço nenhum desses problemas.

De fato, existem motivos razoáveis para suspeitar que é improvável que tais problemas existam. Heuristicamente, a existência de um problema desse tipo provavelmente significaria que a criptografia segura é impossível. Parece um resultado bastante implausível.

Qual é a conexão, você pergunta? Bem, considere qualquer algoritmo aleatório que resolva algum problema com eficiência. Ele se baseia em moedas aleatórias: bits aleatórios obtidos de uma fonte aleatória verdadeira. Agora, suponha que pegemos um gerador pseudo-aleatório de qualidade criptográfica e substituímos a fonte aleatória verdadeira pela saída do gerador pseudo-aleatório. Chame o algoritmo resultante . Note-se que é um algoritmo determinista e seu tempo de execução é aproximadamente o mesmo que . $A$ $A'$ $A'$ $A$

Além disso, se o PRNG criptográfico estiver seguro, heuristicamente devemos esperar que seja um bom algoritmo se for: $A'$ $A$

Por exemplo, se é um algoritmo de Las Vegas (sempre gera a resposta correta e termina rapidamente com alta probabilidade), então será um algoritmo determinístico muito bom (sempre gera a resposta correta e termina rapidamente para a maioria das entradas) . $A$ $A'$
Como outro exemplo, se é um algoritmo de Monte Carlo (tempo de execução determinístico e gera a resposta correta com probabilidade pelo menos ), então será um algoritmo determinístico muito bom (tempo de execução determinístico e gera a resposta correta em uma fração de todas as entradas). $A'$ $1-\varepsilon$ $A$ $1-\varepsilon$

Portanto, se o PRNG criptográfico é seguro e existe um algoritmo aleatório eficiente, você obtém um algoritmo determinístico bastante bom. Agora, existem muitas construções de PRNGs criptográficos que são garantidos como seguros se certas suposições criptográficas se mantiverem. Na prática, essas suposições criptográficas são amplamente aceitas: pelo menos, comércio e transações seguras se baseiam nelas, então aparentemente estamos dispostos a apostar grandes somas de dinheiro que a criptografia segura existe. A única maneira pela qual essa transformação pode falhar é se não existir PRNG criptográfico, o que implica que a criptografia segura é impossível. Embora não tenhamos provas de que esse não seja o caso, parece um resultado improvável.

Detalhes da construção: Veja como funciona. Na entrada , que deriva de uma semente para a PRNG criptográfico como uma função de (por exemplo, por hashing ), e, em seguida, simula , usando a saída do PRNG criptográfico como as moedas para . Por exemplo, uma instanciação específica seria definir , em seguida, usar como a semente do AES256 no modo contador, ou algum outro PRNG criptográfico. Podemos provar as afirmações acima, sob o modelo aleatório do Oracle. $A'$ $x$ $x$ $x$ $A(x)$ $A$ $k=\text{SHA256}(x)$ $k$

Se você não estiver satisfeito com a ideia de que pode gerar resultados incorretos em uma pequena fração de entradas, isso pode ser resolvido. Se você repetir várias vezes e fizer uma votação majoritária, a probabilidade de erro diminuirá exponencialmente rápido no número de iterações. Então, por iteração um número constante de vezes, você pode obter a probabilidade de erro estar abaixo , o que significa que as chances de que você se depara com uma entrada $A'$ $A'$ $\varepsilon$ $1/2^{256}$ $x$ onde o algoritmo gera a resposta errada é muito pequeno (menos do que as chances de ser atingido por um raio várias vezes seguidas). Além disso, com a construção que dei acima, as chances de um adversário encontrar uma entrada onde dá a resposta errada podem ser muito pequenas, pois isso exigiria a quebra da segurança do hash SHA256. (Tecnicamente, isso requer que o modelo de oráculo aleatório justifique, significa que deve ser escolhido para ser "independente" do SHA256 e não codificar os cálculos relacionados ao SHA256, mas quase todos os algoritmos do mundo real satisfazem esse requisito .) $x$ $A'$ $A$

Se você quer uma base teórica forte, você pode iterar vezes, e obter a probabilidade de erro para ser abaixo , onde é o comprimento da entrada . Agora a fracção de entradas -BIT onde dá uma resposta incorrecta é estritamente inferior a . Porém, existem apenas entradas possíveis de bits, e em cada uma delas está correta ou incorreta, portanto, não há entrada em que $A$ $\Theta(n)$ $1/2^n$ $n$ $x$ $n$ $A'$ $1/2^n$ $2^n$ $n$ $A$ $A'$ está incorreto: está correto em todas as entradas e isso é válido incondicionalmente. Se corre no tempo , então corre no tempo , então é um pouco mais lento que mas não muito mais lento. Esse é o conteúdo da prova de Adleman de que o BPP está contido em P / poli. Para propósitos práticos, isso provavelmente é um exagero, mas se você gosta de provas limpas que evitem suposições criptográficas ou se você o aborda da perspectiva de um teórico, talvez você goste mais desta versão. $A'$ $A$ $t(n)$ $A'$ $\Theta(n \cdot t(n))$ $A'$ $A$

Para obter mais detalhes sobre as últimas considerações teóricas e problemas adicionais em que conhecemos um algoritmo aleatório eficiente, mas não conhecemos nenhum algoritmo determinístico que possamos provar ser eficiente, consulte /cstheory//q/31195 / 5038

Em resumo: para qualquer problema em que conheçamos um algoritmo aleatório eficiente, também sabemos de um algoritmo determinístico que parece provável ser eficiente na prática - mas, atualmente, não sabemos como provar que é eficiente. Uma possível interpretação é que não somos muito bons em provar coisas sobre algoritmos.

DW
fonte