Computação Quântica/Capítulo 3/Exercícios: mudanças entre as edições
imported>Alexandre146 |
imported>Karinina |
||
Linha 14: | Linha 14: | ||
[[Imagem:NAND=XOR.jpg]] | [[Imagem:NAND=XOR.jpg]] | ||
=== 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, | |||
-> <math>x \in L3</math> se somente se <math>R2(x) \in L2</math> | |||
-> <math>x \in L2</math> se somente se <math>R1(x) \in L1</math> | |||
* 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 <math>x \in L3</math> então <math>y1 \in L2</math> e consequentemente <math>y \in L1</math>, por outro lado se <math>x \notin L3</math> então <math>y \notin L2</math> e consequentemente <math>y \notin L1</math>. | |||
Portanto, pelo algoritmo acima vale a propriedade <math>x \in L3</math> se e somente se <math>R(x) \in L1</math>. Logo o algoritmo é polinomial e consequentemente L1 é redutível para L3. |
Edição das 18h03min de 17 de julho de 2005
Exercícios Cap.3 - Introdução à Ciência da Computação
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.