Upload
ramon-santos
View
24
Download
2
Embed Size (px)
Citation preview
Decidibilidade e Reducao de Problemas
Ramon Santos Nascimento
Universidade Federal Rural de Pernambuco
27 de Janeiro de 2014
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 1 / 11
Decidibilidade
Definicao
Um problema e decidıvel se sua solucao e encontrada por umaMaquina de Turing que retorna uma resposta;
Caso contrario, o problema e indecidıvel.
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 2 / 11
Problema de aceitacao - Linguagens recursivas
Seja U uma M.T .U. com entrada < M, ω >:
ACEITA: Se M em algum momento entra no seu estado de aceitacao;
REJEITA: Se M em algum momento entra em estado de rejeicao.
E decidıvel.
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 3 / 11
Problema de aceitacao - Linguagens recursivamenteenumeraveis
Seja U uma M.T .U. com entrada < M, ω >:
ACEITA: Se M em algum momento entra no seu estado de aceitacao;
REJEITA: Se M em algum momento entra em estado de rejeicao ouse M entra em loop.
E indecidıvel.
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 4 / 11
Hierarquia de Chomsky
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 5 / 11
Redutibilidade
Definicao
E uma maneira de converter um problema em outro de forma que umasolucao para o segundo problema possa ser usada para resolver o primeiro.
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 6 / 11
Redutibilidade
Sejam os problemas A e B.
Se A se reduz a B, podemos usar uma solucao de B para resolver A.
Teorema 1
Se A e redutıvel a B (A ≤ B) e B e decidıvel entao A e decidıvel.
Teorema 2
Se A e redutıvel a B (A ≤ B) e A e indecidıvel entao B e indecidıvel.
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 7 / 11
Redutibilidade por mapeamento
Significa que existe uma funcao computavel que converte instancias doproblema A para instancias do problema B.
Sejam as Linguagens A e B, A e redutıvel por mapeamento a B (A ≤m B),se existe uma funcao computavel f :
∑∗− >∑∗, onde para toda ω,
ω ∈ A↔ f (ω) ∈ B
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 8 / 11
A importancia dos assuntos
Saber se um problema e decidıvel.
E se nao for, o que fazer?
Usar Redutibilidade para provar que um problema e indecidıvel.
Como?
Usar Redutibilidade para resolver problemas.
Como?
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 9 / 11
Duvidas
Duvidas?
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 10 / 11
Obrigado
Obrigado!
Ramon Santos Nascimento (UFRPE) Decidibilidade e Reducao de Problemas 27 de Janeiro de 2014 11 / 11