Computação Quântica/Capítulo 3/Exercícios
Exercícios Cap.3 - Introdução à Ciência da Computação
Volte para a página principal do livro clicando aqui: Computação_Quântica
Exercicío 3.8 (Universalidade de NAND) Mostre que a porta NAND pode ser usada para simular as portas AND, XOR e NOT, utilizando também fios, bits de trabalho (ancilla) e FANOUT.
- A porta NOT pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.
- A porta AND pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.
- A porta XOR pode ser simulada através do circuito apresentado na figura abaixo, onde também podemos ver a tabela verdade deste.
Exercicío 3.21 Mostre que se uma linguagem L1 é redutível para a linguagem L2 e a linguagem L2 é redutível para a linguagem L3, então L1 é redutível para a linguagem L3.
- Por hipótese existem reduções polinomiais R1 e R2 tal que,
-> se somente se
-> se somente se
- Considerando o seguinte algoritmo:
R(x)
y1 <- R2(x)
y <- R1(y1)
return y
- Pela propriedade do algoritomo que usa R1 e R2 sabemos que se então e consequentemente , por outro lado se então e consequentemente .
Portanto, pelo algoritmo acima vale a propriedade se e somente se . Logo o algoritmo é polinomial e consequentemente L1 é redutível para L3.
Volte para a página principal do livro clicando aqui: Computação_Quântica