Lista 6

1. Seja L uma linguagem e L' o seu complemento. Mostre que se L é NP-completa então L' é coNP-completa.

2. Mostre que se uma linguagem NP-completa está em coNP então NP=coNP.

3. Seja M uma MTP que mostra que uma certa linguagem L está em BPP, ou seja, M é polinomial e tal que
   se x está em L então Pr[M(x)=SIM] >= 3/4,
   se x não está em L então Pr[M(x)=NÃO] >= 3/4.
   Neste caso, dizemos que M tem probabilidade de erro de 1/4.
   (Técnica de amplificação das probabilidades) Mostre que, dada uma M como acima e um número arbitrário eps>0, podemos obter uma MTP com probabilidade de erro no máximo eps.
   Sugestão: Use a conhecida delimitação de Chernoff. Uma versão simplificada dessa delimitação, adequada ao exercício acima, é dada pelo teorema abaixo. Execute várias vezes M e responda a resposta que sair mais nas várias rodadas.

   Teorema: Para i=1,...,n, seja X_i uma variável aleatória que assume valor 1 com probabilidade p e 0 com probabilidade 1-p. Então se X é a soma dos X_i, m=np (m é o valor esperado de X) e d é um inteiro positivo arbitrário, temos que Pr[X > (1+d)m] < (e^d/(1+d)^1+d)^m

4. (11.5.13 e 14) Mostre que RP e BPP são fechadas por reduções, por união e por intersecção.
   Dica: Para BPP, utilize o resultado do exercício anterior.

5. (11.5.18) Mostre que, se NP está contida em BPP, então RP = NP. (Ou seja, se SAT pode ser resolvido por um algoritmo BPP, então ele pode ser resolvido por um algoritmo Monte Carlo sem falsos positivos.)
   Sugestão: Considere uma fórmula SAT com n variáveis e uma MTP BPP M para SAT.
   Prove um resultado um pouco mais forte que o do exercício 3 (a prova é basicamente a mesma que a do exercício 3): prove que é possível, a partir de M, conseguir uma MTP que consome tempo polinomial em n com probabilidade de erro no máximo 1/n².
   Use tal máquina para indicar qual é a atribuição correta para a fórmula, derivando uma MTP RP para SAT.

6. (11.5.12) Escreva cada um dos problemas abaixo como uma linguagem e mostre cada um deles é indecidível.
   • É verdade que, para todas as entradas, ou todas as computações rejeitam ou pelo menos metade delas aceitam?
   • É verdade que, para todas as entradas, ou pelo menos 3/4 das computações rejeitam ou pelo menos 3/4 das computações aceitam?
   • É verdade que, para todas as entradas, pelo menos uma computação aceita?
   • Dadas duas MTND, é verdade que, para todas as entradas, ou a primeira tem uma computação que aceita ou a segunda, mas não ambas?

7. (11.5.8)
   • Mostre que o algoritmo de Euclides pode ser modificado para, dados dois inteiros positivos x e y, calcular dois inteiros positivos A e B tais que Ax+By=mdc(x,y). (Dica: suponha que você sabe estes números, digamos A' e B', para y e x mod y. Deduza o valor de A e B, eventualmente usando o valor de x/y.)
   • Baseado no item anterior, mostre que, dado n e um m tal que mdc(m,n)=1, pode-se calcular o inverso de m mod n (isto é, o número k tal que km=1 mod n) em O(log³ n) passos.

8. Mostre que BPP está contido em PSPACE.