Redutibilidade-0.51

Prévia do material em texto

Teoria da Computação 
Redutibilidade 
Versão dos Slides: 0.51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redução 
 Redução é uma maneira de converter um 
problema em um segundo problema de 
maneira que a solução deste segundo 
problema possa ser usada diretamente para 
produzir a solução do problema original 
 Por exemplo, o problema de medir a área de 
um retângulo reduz-se ao problema de medir 
a altura e a largura do retângulo 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redução 
 Ocorre não apenas em modelos matemáticos 
abstratos mas também em várias situações da 
vida real 
• O problema de viajar de carro de Lavras para Belo 
Horizonte reduz-se ao problema de chegar até a BR 
381 
• O problema de viajar para Europa reduz-se ao 
problema de conseguir dinheiro para estadia e 
passagem 
• O problema de conseguir dinheiro reduz-se ao 
problema de encontrar um emprego 
 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redução 
 Redução tem um papel fundamental na 
classificação de problemas em termos de 
decidibilidade e complexidade 
 Quando A é reduzível a B, resolver A não pode 
ser mais difícil que resolver B porque a 
solução de B implica na solução de A 
• Notem que não estamos fazendo qualquer 
afirmação a respeito da solução de 𝐴 ou 𝐵 em 
isolamento 
4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redução: Computabilidade 
 Se A é reduzível a B e B é decidível, então A 
também é decidível 
 Se A é reduzível a B e A é indecidível, então B 
também é indecidível 
• Método para provar indecidibilidade: para provar que 
um problema é indecidível basta mostrarmos que um 
outro problema conhecidamente indecidível reduz-se 
a ele 
• Entretanto, note que mostrar que um problema A se 
reduz a outro problema indecidível não é suficiente 
para provar indecidibilidade de A 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Problemas Indecidíveis 
 Nós já sabemos que 𝐿𝑀𝑇 , o problema de se 
determinar se uma MT aceita ou rejeita uma 
determinada entrada, é indecidível 
 Vamos considerar o problema similar 𝐻𝐿𝑇𝑀𝑇, 
que é o problema de determinar se uma MT 
pára (aceitando ou rejeitando) em uma dada 
entrada 
• Ou seja, dicotomia Pára/Loop 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1 
 𝐻𝐿𝑇𝑀𝑇 =
𝑀, 𝑝 | 𝑀 é 𝑢𝑚𝑎 𝑀𝑇 𝑒 𝑀 𝑝á𝑟𝑎 𝑛𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑝 
 𝐻𝐿𝑇𝑀𝑇 é indecidível 
 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova (1) 
 Idéia: Prova por contradição 
 Assumimos que 𝐻𝐿𝑇𝑀𝑇 é decidível; depois 
mostramos que 𝐿𝑀𝑇 é reduzível a 𝐻𝐿𝑇𝑀𝑇, o 
que não é possível visto que 𝐿𝑀𝑇 é indecidível 
 Vamos assumir que temos uma MT 𝑅 que 
decide 𝐻𝐿𝑇𝑀𝑇. Neste caso podemos construir 
uma MT 𝑆 que decide 𝐿𝑀𝑇 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova (2) 
 Quando 𝑆 recebe uma entrada 𝑀, 𝑝 , 𝑆 deve 
aceitar se 𝑀 aceita 𝑝 e deve rejeitar se 𝑀 rejeita 
𝑝 ou entra em loop 
 Podemos usar R como uma macro de S para 
testar se 𝑀 irá parar. Se 𝑅 mostrar que 𝑀 não 
pára, então 𝑆 rejeita; caso contrário podemos 
executar 𝑆 normalmente na entrada 𝑀, 𝑝 
 Neste caso teríamos que S é um decididor. 
Entretanto, sabemos que 𝐿𝑀𝑇 é indecidível e que 
𝑆 não existe . Portanto, 𝑅 também não existe 
9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 1: Prova 
 Vamos assumir que uma MT 𝑅 decide 𝐻𝐿𝑇𝑀𝑇. 
Nós construímos uma MT S decidindo 𝐿𝑀𝑇. 
 S = “Na entrada 𝑀, 𝑝 : 
1. Execute 𝑅 na entrada 𝑀, 𝑝 
2. Se 𝑅 rejeitar, Rejeita 
3. Se 𝑅 aceitar, simule M em p até M parar 
4. Se M aceitou, Aceita. Se M rejeitou, Rejeite 
 Claramente, se R decide 𝐻𝐿𝑇𝑀𝑇, então S 
decide 𝐿𝑀𝑇. Entretanto, como 𝐿𝑀𝑇 é 
indecidível, então 𝐻𝐿𝑇𝑀𝑇 também é 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2 
 𝐸𝑀𝑇 = 𝑀 | 𝑀 é 𝑢𝑚𝑎 𝑀𝑇 𝑒 𝐿 𝑀 = ∅ 
 Teorema 2: 𝐸𝑀𝑇 é indecidível 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova 
 Idéia: Assumimos que 𝐸𝑀𝑇 é decidível e então 
demonstramos que 𝐿𝑀𝑇 é decidível, o que 
constitui uma contradição 
 Seja 𝑅 uma MT que decide 𝐸𝑀𝑇. Vamos usar 𝑅 
para construir uma MT 𝑆 que decide 𝐿𝑀𝑇 
 Note que simplesmente invocar R de S não 
resolve: 
• Se 𝑅 rejeitar uma entrada 𝑀 , tudo o que 
sabemos é que 𝐿 𝑀 ≠ ∅ 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova (2) 
 Vamos executar 𝑅 em uma versão modificada 
de 𝑀: 
• 𝑀 rejeita diretamente todas palavras exceto p; 
quando a entrada é 𝑝, 𝑀 comporta-se 
normalmente 
 Usamos 𝑅 para testar se a MT modificada 
aceita a linguagem vazia 
• A linguagem será não-vazia sse a MT original 
aceita 𝑝 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova (3) 
 Seja 𝑀1 a 𝑀𝑇 modificada 
 𝑀1 = "𝑁𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑥: 
1. Se 𝑥 ≠ 𝑝, Rejeita 
2. Se 𝑥 =p, execute 𝑀 com entrada 𝑝 e aceite se 𝑀 
aceita 𝑝“ 
 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 2: Prova (4) 
 Agora estamos prontos para contruir 𝑆 
 𝑆 = "𝑁𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑀, 𝑝 , onde 𝑀 é a 
codificação de uma MT e 𝑝 uma palavra 
1. Use a descrição de 𝑀 e 𝑝 para construir a MT 𝑀1 
2. Execute 𝑅 na entrada 𝑀1 
3. Se 𝑅 aceita, Rejeita; se R rejeita, Aceita 
 Note que para contruir 𝑀1 é necessário apenas 
adicionar estados extras para testar se 𝑥 = 𝑝 
 Portanto, se 𝑅 é um decididor para 𝐸𝑀𝑇 , então 
S é um decididor para 𝐿𝑀𝑇. Como 𝐿𝑀𝑇 é 
indecidível, então 𝑅 não pode existir 
 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova: Receita de Bolo 
 Como padrão geral para provas usando 
redutibilidade, nós mostramos que a construção 
de um decididor 𝑆 para 𝐿𝑀𝑇 se reduz à 
construção de um decididor 𝑅 para a linguagem 
que queremos provar que é indecidível 
 Generalizando esta estratégia, podemos usar 
qualquer problema reconhecidamente indecidível 
para provar que outro problema também é 
indecidível através da técnica de redutibilidade 
 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3 
 𝐸𝑄𝑀𝑇 =
𝑀1, 𝑀2 | 𝑀1 𝑒 𝑀2 𝑠ã𝑜 𝑀𝑇𝑠 𝑒 𝐿 𝑀1 = 𝐿 𝑀2 
 𝐸𝑄𝑀𝑇 é indecidível 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3: Prova 
 Idéia: Vamos simplesmente mostrar que 𝐸𝑀𝑇 
é reduzível a 𝐸𝑄𝑀𝑇. 
 Para isso podemos demonstrar que 𝐸𝑀𝑇 é na 
verdade um caso especial de 𝐸𝑄𝑀𝑇, e, 
portanto um decididor para 𝐸𝑄𝑀𝑇 também é 
um decididor para 𝐸𝑀𝑇 
 Exercício: Como isto poderia ser feito? 
 
 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3: Prova (2) 
 Considere o caso em que 𝐿 𝑀1 = ∅ 
 Então, decidir se 𝐿 𝑀1 = 𝐿 𝑀2 consiste em 
decidir se 𝐿 𝑀2 = ∅ 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 3: Prova (2) 
 Seja 𝑅 uma 𝑀𝑇 que decide 𝐸𝑀𝑇, construa uma 
MT 𝑆 que decida um caso especial de 𝐸𝑄𝑀𝑇 da 
seguinte maneira: 
 𝑆 = "𝑁𝑎 𝑒𝑛𝑡𝑟𝑎𝑑𝑎 𝑀 , 𝑜𝑛𝑑𝑒 𝑀 é 𝑢𝑚𝑎 𝑀𝑇 
1. Execute 𝑅 na entrade 𝑀, 𝑀1 , 𝑜𝑛𝑑𝑒 𝑀1 é uma MT 
que rejeita todas entradas (𝐿 𝑀1 = ∅) 
2. Se 𝑅 aceita, Aceita; se 𝑅 rejeita, Rejeita” 
 Se R decide 𝐸𝑀𝑇, então S decide um caso 
especial 𝐸𝑄𝑀𝑇 . Mas 𝐸𝑀𝑇 é indecidível, então 
𝐸𝑄𝑀𝑇 deve ser também indecidível 
 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home 
 Note que redutibilidade é similar à relação ≤ 
em termos de complexidade 
 Um problema A ser reduzível a um problema 
B, significa que a dificuldade em resolver A é 
menor ou igual a dificuldade em resolver B 
 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (2) 
22 
Problema A Problema B reduzível a 
Decidível 
Problema A Problema B reduzível a 
Decidível Decidível 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (3) 
23 
Problema A Problema B reduzível a 
Decidível 
Problema A Problema B reduzível a 
Decidível Decidível 
X B pode ser indecidível! 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home(4) 
24 
Problema A Problema B reduzível a 
Indecidível 
Problema A Problema B reduzível a 
Indecidível Indecidível 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (5) 
25 
Problema A Problema B reduzível a 
Indecidível 
Problema A Problema B reduzível a 
Indecidível Indecidível 
X A pode ser decidível! 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (6) 
26 
Estratégias para demonstrar 
redutibilidade e provar indecidibilidade 
Problema A 
Indecidível 
Problema B 
Sabemos que Problema A é indecidível. 
Queremos reduzir o Problema A ao Problema B 
para demonstrar que B também é indecidível 
reduzível a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (7) 
27 
Estratégia 1: Assuma que um decididor DB para 
B existe. Mostre que usando DB podemos 
contruir um decididor DA para A (contradição) 
Decididor DA 
Decididor DB 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take-Home (8) 
28 
 Estratégia 2: Assuma que um decididor DB 
para B existe. Mostre que este decididor 
deverá necessariamente conter um decididor 
DA (contradição) para tratar um caso especial 
do problema B 
Decididor DB 
Decididor DA 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções Computáveis Totais 
 Definição: Uma função 𝑓: Σ∗ ⟶ Σ∗ é uma 
função computável total se existe alguma 
MTN que termina sua computação com 
sucesso (configuração de aceitação) para 
qualquer 𝑝 ∈ Σ, e o conteúdo final da fita é 
dado por ˽𝑓 𝑝 ˽ 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Intuição de Redutibilidade 
 A redução de um problema 𝐴 para um 
problema 𝐵 significa que existe uma função 
computável total que converte instâncias do 
problema 𝐴 em instâncias do problema 𝐵 
• Desta maneira, qualquer instância do problema 𝐴 
pode ser resolvida usando a redução para 
converte-la em uma instância do problema 𝐵 e, 
então, usar uma MT que resolve o problema 𝐵 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Funções Computáveis e MTs 
 Funções computáveis podem ser 
transformações de descrições de MTs 
 Por exemplo, uma função computável total 𝑓 
recebe com entrada 𝑝 e retorna a descrição de 
uma MT 𝑀′ se 𝑝 = 𝑀 é a codificação de 
uma MT 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de Redutibilidade 
 A definição formal de redutibilidade em 
termos de linguagens é dada da seguinte 
forma: 
 Definição: Linguagem 𝐴 é reduzível para a 
linguagem 𝐵, denotado por A ≤𝑟 𝐵, se existe 
uma função computável total 𝑓: Σ∗ ⟶ Σ∗, 
onde para qualquer 𝑝 temos que: 
𝑝 ∈ 𝐴 ↔ 𝑓 𝑝 ∈ 𝐵 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redutibilidade de Linguagens 
 A redução de 𝐴 para 𝐵 provê uma maneira de 
converter questões a respeito dos elementos de 
A em questões a respeito dos elementos de B 
• Para testar se 𝑝 ∈ 𝐴, a redução 𝑓 é primeiramente 
usada para mapear 𝑝 para 𝑓(𝑝); então é testado se 
𝑓(𝑝) ∈ 𝐵 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4 
 Se 𝐴 ≤𝑟 𝐵 e B é decidível, então A é decidível 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4 - Prova 
 Seja 𝑀 o decididor para 𝐵 e 𝑓 a redução de 𝐴 
para 𝐵. Um decidior para 𝑁 para 𝐴 pode ser 
descrito da seguinte maneira: 
 N=“Na entra p: 
1. Compute 𝑓(𝑝) 
2. Execute 𝑀 na entrada 𝑓(𝑝) e retorne como 
resultado o que 𝑀 retornar” 
 Claramente, se 𝑝 ∈ 𝐴, então 𝑓 𝑝 ∈ 𝐵 porque 𝑓 
é uma redução de 𝐴 para 𝐵. Assim 𝑀 aceita 𝑓(𝑝) 
sempre que 𝑝 ∈ 𝐴 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Corolário 1 
 Se 𝐴 ≤𝑟 𝐵 e 𝐴 é indecidível, então 𝐵 é 
indecidível 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5 
 Se Se 𝐴 ≤𝑟 𝐵 e B é Turing-reconhecível, então 
A é Turing-reconhecível 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Históricos da Computação 
 O histórico da computação de uma Máquina de Turing para 
uma determinada entrada é simplesmente a sequência de 
configurações que a máquina percorre durante o 
processamento da entrada 
• Registro completo da computação da máquina 
 O histórico de computação pode ser usado para provar que 
𝐿𝑀𝑇 é reduzível a certas linguagens 
• Útil quando a prova de indecidibilidade envolve testar a 
existência de alguma coisa (e.g., encontrar a raiz integral de 
polinômios) 
 Além disso, históricos de computação também podem ser 
usado para provar decididibilidade 
 A seguir, vamos mostrar uma prova de decidibilidade 
usando históricos 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
 Seja 𝑀 uma MT e 𝑝 a palavra de entrada 
 Histórico de computação de aceitação para 𝑀 
em 𝑝: uma sequência de configurações 
𝐶1, 𝐶2, … , 𝐶𝑙, onde 𝐶1 é o estado de configuração 
de M na entrada p, 𝐶𝑙 é uma configuração de 
aceitação de M, e cada 𝐶𝑖 produz a configuração 
𝐶𝑖+1 
 Histórico de computação de rejeição para 𝑀 em 
𝑝: definido de maneira análoga, com diferença 
que 𝐶𝑙 agora é um estado de rejeição 
 
 
 
 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
 Note que os históricos de computação de 
aceitação e rejeição são sequências finitas 
 Para máquinas determinísticas existe apenas 
um histórico de computação para dada 
entrada 
 Para máquinas não-determinísticas podem 
existir muitos históricos de computação para 
uma mesma entrada 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Autômato 
Limitado Linearmente (ALL) 
 Um tipo de MT restrito onde a cabeça l/e não 
pode mover uma determinada distância além 
da porção da fita que contém a entrada 
 Necessariamente, um ALL é uma MT com uma 
quantidade limitada de memória 
• Para uma entrada de tamanho 𝑛, a quantidade de 
memória necessária é linear em 𝑛 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Linguagens e Máquinas 
42 
Linguagens Máquinas 
Recursivamente 
Enumeráveis 
Máquina de Turing, 
Máquina de Turing 
Não-Determinística 
Sensitivas ao 
Contexto 
Autômato Limitado 
Linearmente 
Livres de 
Contexto Autômato de Pilha 
Regulares 
Autômato Finito 
Determinístico, Automato 
Finito Não-Determinístico 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5 
 𝐿𝐴𝐿𝐿 = 𝑀1, 𝑝 | 𝑀1 é 𝑢𝑚 𝐴𝐿𝐿 𝑞𝑢𝑒 𝑎𝑐𝑒𝑖𝑡𝑎 𝑝 
 𝐿𝐴𝐿𝐿 é decidível 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5: Prova 
 Para decidir se um 𝐴𝐿𝐿 𝑀 aceita uma entrada 
𝑝, temos que construir uma MT 𝑆 para simular 
𝑀 em 𝑝. Durante a simulação, se 𝑀 pára e 
aceita, 𝑆 aceita; se 𝑀 pára e rejeita, 𝑆 rejeita 
 O problema é se M entrar em loop 
 Como poderiámos detectar se M entrou em 
loop 
• O fato da memória de M ser limitada pode ajudar 
nesta tarefa? 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Décimo Problema de Hilbert 
 Por simplicidade, considere uma versão mais 
simples do polinômio contendo apenas uma 
variável, como 4𝑥3 − 2𝑥2 + x − 7 
 Seja D1 = {𝑝|𝑝 é um polinômio sobre x com uma 
raiz integral} 
 A MT 𝑀1 reconhece 𝐷1 
 𝑀1= A entrada é um polinômio p sobre a variável 
x 
1. Avalia p com a variável x atribuída sucessivamente 
os valores 0, 1, -1, 2, -2, 3, -3, … Se a qualquer ponto 
o resultado do polinômio é 0, aceite 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Décimo Problema de Hilbert 
 Para o problema específico de encontar uma raiz 
integral de polinômios contendo apenas uma 
variável, é possível projetar uma MT decididora 
• É conhecido que a raiz do polinômio, se existir estar 
no intevalo ±𝑘
𝑐𝑚𝑎𝑥
𝑐1
, onde 𝑘 é o número de termos do 
polinômio, 𝑐𝑚𝑎𝑥 é o coeficiente com o maior valor 
absoluto, e 𝑐1 é o coeficiente do termo de maior 
ordem 
 Se uma raiz não é encontrada dentro destes 
limites, então a máquina rejeita 
 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lemma 1 
 Seja 𝑀 um 𝐴𝐿𝐿 com 𝑞 estados e 𝑔 símbolos 
no alfabeto da fita. Então, existem exatas 
𝑞𝑛𝑔𝑛 configurações distintas para uma fita de 
tamanho 𝑛 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lemma 1: Prova 
 Uma configuração consiste do estado de controle,posição da cabeça l/e, e o conteúdo da fita. Aqui, 
existem 𝑞 estados. 
 O tamanho da fita é 𝑛, então a cabeça pode estar 
em 𝑛 posições, e 𝑔𝑛 possíveis palavras de 
símbolos do alfabeto da fita podem aparecer na 
fita. 
 O produto destas três quantidades é o número 
total de diferentes configurações de 𝑀 com uma 
fita de tamanho 𝑛 
 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 5: Prova 
 Idéia: Vamos “observar“ M por 𝑞𝑛𝑔𝑛 
configurações. Caso não páre durante este 
intervalo, então M está necessariamente 
repetindo configurações o que caracteriza um 
loop 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teorema 4: Prova 
 S = “Na entrada 𝑀, 𝑝 , onde 𝑀 é um 𝐴𝐿𝐿 e 
𝑝 é uma palavra: 
1. Simule 𝑀 em 𝑝 por 𝑞𝑛𝑔𝑛 até que 𝑀 páre 
2. Se 𝑀 parou, Aceite se 𝑀 aceitou, Rejeite se 𝑀 
rejeitou. Caso contrário, Rejeite 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Take Home (8) 
 Provas de decidibilidade podem ser realizadas 
atráves do estabelecimento de um limite para 
o processamento de uma MT 
• Após este limite a entrada é imediatamente 
rejeitada 
 
 
51