6.045J/18.400J: Autômatos, Computabilidade e Complexidade
Prof. Ron Rivest
Exame Final
Este teste terá 3 horas de duração. Você pode usar a bibliografia recomendada (“Introdução
à Teoria da Computação”, de Sipser) e as suas anotações (incluindo os folhetos da aula,
soluções de problema etc). Não será permitido o uso de outros materiais de consulta.
!!! Certifique-se de escrever o seu nome completo nesta e em todas as outras páginas!!!
Nome:
19-1
Problema 1: Perguntas para respostas rápidas: (3 pontos cada)
1 – Suponha que L seja uma linguagem e M seja um decididor de tempo polinomial probabilístico
tal que
aceite
.
.
e
É
.aceite
? (explique em poucas palavras).
2. Suponha que a linguagem L seja a união das sublinguagens L1, L2,
,onde o número
dessas sublinguagens possa ser finito ou infinito e onde cada linguagem Li seja conhecida
como regular. Quão difícil pode ser reconhecer L? (O que pode ser pior, devido a essas
limitações?)
3. Devido a limitações de fabricação, as máquinas de Turing produzidas pela ACME
n
Computer estão limitadas a uma fita, com o máximo de 2 quadrados de fita, quando a
entrada tiver o tamanho n. É possível selecionar o problema de parada (Halting) de uma TM
ACME? (Explique em poucas palavras.)
4. É verdadeiro que, se P = NP, então
palavras) o porquê?
. Você pode explicar (em poucas
5. Verdadeiro ou falso: é impossível um esquema de criptografia determinístico ser
semanticamente seguro. (Explique em poucas palavras.)
Problema 2: (15 pontos) A operação de shuffle (ordenação ou embaralhamento aleatório) é
importante no estudo de sistemas concorrentes. Se
, então
é conjunto de todas
as strings que podem ser obtidas por meio de ordenação aleatória (shuffling) de x e y juntos,
como em um maço de cartas. Por exemplo,
A ordenação aleatória das duas linguagens A e B, simbolizada como
é o conjunto de
strings obtidas pela ordenação aleatória de uma string de A com uma string de B:
Prove que, se A e B são regulares, então
FA que reconheça
também é regular. (Dica: você pode projetar um
)?
Problema 3: (15 pontos) Um dos dois conjuntos a seguir pode ser reconhecido por Turing, ao
passo que o outro não. Qual corresponde a qual? Prove que a sua resposta está correta. (Dica:
você pode provar que não é possível reconhecer os dois?)
aceita no máximo 481 entradas distintas
aceita mais de 481 entradas distintas
Problema 4: (15 pontos) Considere o problema de conjunto de vértices de feedback
(FEEDBACK VERTEX SET):
A partir de um grafo direcionado G = (V, E) e de um número
tal que
, existe um subconjunto
e F contenham um vértice de cada ciclo direcionado em G?
Demonstre que o problema FEEDBACK VERTEX SET é NP-complete. (Dica:
considere VC.)
.
Problema 5: (15 pontos) Demonstre que, se P=NP, existe um algoritmo de tempo
polinomial que utiliza uma instância
do problema FEEDBACK VERTEX SET (conforme
definido no problema anterior deste exame final) e o qual retorna
•
Um conjunto de vértices de feedback no tamanho máximo de K (se existir algum) ou
•
Um caractere especial
(caso contrário).
Problema 6: (15 pontos) Suponha que
e M sejam um decididor de tempo
polinomial probabilístico, de modo que
aceite
e
aceite
(Aqui, as probabilidades dependem, como sempre, apenas dos movimentos internos da
moeda da máquina M.) Suponha que, em qualquer entrada x, a máquina M nunca gire
moedas (isto é, nunca use mais de
mais de
bits de
aleatoriedade).
Demonstre que
.
Problema 7: (15 pontos) Suponha que tenhamos um algoritmo de chave pública, um tríplice
de algoritmos de tempo polinomial (G,E,D), de forma que
•
G seja um algoritmo de geração de chaves aleatórias que produza pares de chave
(PK,SK) quando é dado como entrada um “parâmetro de segurança” k (em unário,
k
como 1 , o mais usual),
•
E corresponda a um algoritmo de criptografia aleatória que utiliza uma chave pública
PK e uma mensagem
, e que produza um texto cifrado
em
•
D seja um algoritmo de decodificação que utiliza um suposto texto cifrado C em
e uma chave secreta SK, produzindo um destes resultados:
•
M, se C tiver sido produzido por E(PK,M) (para o PK associado ao SK), ou
•
Um caractere especial
(em caso contrário).
Definimos um algoritmo de chave pública (G,E,D) como “simplesmente seguro” (uma noção mais
simples do que semanticamente seguro”) se, para todas as mensagens M0, M1 em {01}*, para
todos os adversários de tempo polinomial probabilístico A, e para todos os parâmetros de
segurança suficientemente completos k,
significa que b é escolhido de forma uniforme aleatória a partir do conjunto
Aqui,
Suponha também que houvesse um adversário que fosse capaz de, em pelo menos dois
terços do tempo, decodificar um bit de mensagem duplamente criptografado (0 ou 1). Ou seja,
suponha que exista um adversário
em tempo polinomial probabilístico tal que, para todo k
Demonstre que o esquema de criptografia (G,E,D) não é simplesmente seguro. (Dica: se você
tivesse
, como iria distinguir E(PK,0) de E(PK,1)?)