Intratabilidade

Yuri tavares dos Passos

MT limitada por tempo

● Dada uma entrada de tamanho n. Uma MT que sempre pára dentro de T(n) movimentos é dita limitada por um tempo T(n).– Esta MT pode possuir múltiplas fitas.

– Pode ser não determinística.

● O caso deteminístico e multifita corresponde a uma algoritmo de tempo de execução T(n).

A classe P

● Se uma MT determinística M é limitada por um tempo polinomial T(n), então dizemos que M é limitada por tempo polinomial.– T(n) = O(nk), para um k constante.

● Assim, L(M) pertence a classe P.● Quando falamos de P, não estamos

falando de um algoritmo que roda em computador ou em uma MT.

Equivalência polinomial de computadores e MT● Como foi discutido sobre a conversão

entre MT multifita e computadores, vimos que uma algoritmo que roda em tempo O(T(n)) em um PC roda em tempo O([T(n)]2) em uma MT multifita.

● Se T(n) é um polinômio, [T(n)]2 também é.

Exemplos de problemas em P● Dado uma sequência de números, ela está

ordenada?● Dado uma palavra w, ela pertence a uma

gramática G?– Algoritmo CYK executa em tempo O(n3)

● Dado um grafo G, nós x e y, existe uma caminho de x a y?– Algoritmo de Djikstra executa em tempo O(n log n),

para n nós.

Tempo de execução entre polinômios.● O(n log n) não é um polinômio.● Mas para pertencer a P, basta que seja

limitada por um polinômio.● O(n log n) < O(n2)

A classe NP

● O tempo de execução de uma MT não-determinística é o número máximo de passos tamados ao longo de qualquer ramo.

● Se este tempo é limitado por um polinômio, então a MT não determinística é dita limitada por um tempo polinomial.

● Sua linguagem/problema é dito estar em uma classe NP.

Definição alternativa de NP● A classe NP pode ser definida como a classe dos

problemas que possuem um verificador que executa em tempo polinomial.

● Um verificador é um algoritmo que verifica se uma entrada w, de tamanho n, possui uma propriedade c.– Formalmente, um verificador V é um algoritmo que aceita

<w,c>.

– Assim, um problema A pode ser enunciado como:● A = {w| V aceita <w,c> para alguma cadeia c}

– A é NP se V executa em tempo polinomial.

Exemplo 1

● Saber se um número x é composto, ou seja, existem dois números inteiros positivos maiores que 1, p e q, tais que x=pq.– COMPOSTO = {x| x=pq, para inteiros p,q > 1}

● Verificar se um x pertence a COMPOSTO pode ser feito em tempo polinomial. Basta fornecer x e um de seus divisores (p ou q).– V verificará a entrada <x,p>.

● Contudo, verificar se x pertence a COMPOSTO também pode ser feito em tempo polinomial em uma MT determinística.

Exemplo 2

● Um caminho hamiltoniano em um grafo direcionado G é um caminho que passa por todos os nós de G somente uma vez.– CAMHAM = {<G,s,t> | G é um grafo

direcionado com um caminho hamiltoniano de s para t}

Exemplo 2

Exemplo 2

● Um verificador V para <G,s,t> seria utilizado junto com um caminho C. Assim a verificação seria apenas comparar se C é um caminho se s a t que passa somente uma vez em cada nó.– V verificaria a entrada <G,s,t,C>.

● CAMHAM é um problema que ainda não sabem se possui uma MT determinística que resolva em tempo polinomial.

Equivalência das definições

w

|w| = n

O(nk) = T(n)

Verificador

aceitarejeita

...

c|c| = O(nk)

Equivalência das definições

w

|w| = n

...

c

...

|c| = O(nk)

NTM executa até encontrar um certificado igual a c

c1

c2

cn

P e NP

● Um dos problemas aberto da computação é:– P = NP?

● Há milhares de problemas que estão em NP, mas não parecem estar em P.

● Mas também não há provas de que não estejam em P.

Problemas completos

● Uma maneira de descobrir se P = NP é identificar os problemas completos para NP.

● Um problema é NP-completo se ele tem a propriedade de, caso pertencer a P, todos os problemas em NP também serão P.

● Esta definição é feita formalmente usando uma redução de tempo polinomial.

Problemas completos – intuição● Um problema completo para uma classe

engloba todo problema em uma classe, mesmo se ele não parece englobar.

● Verificar se uma expressão booleana, composta por E, OU e NÃO possui algum resultado verdadeiro engloba qualquer problema a respeito de MT.

Redução de tempo polinomial● Semelhante as reduções feitas para

descobrir a (in)decibilidade dos problemas.● Mas agora com a restrição de levar um

tempo polinomial para fazer as conversões entre cadeias.

Conversão em tempo polinomialw x

Redução de tempo polinomial● Objetivo: encontrar uma maneira de

mostrar que o problema L é NP-completo reduzindo todo problema em NP para L de tal forma que se nós tivermos um algoritmo de tempo polinomial para MT determinísticas que decida L, então nós podemos construir um algoritmo de tempo polinomial para qualquer problema em NP.

Redução de tempo polinomial

Redução de tempo polinomial

NP

Um problemaNP-completo

.

. . .

.

...

.

. Um problema NP

Redução de tempo polinomial● Precisamos da noção de um tradutor de

tempo polinomial, ou seja, uma MT que:– Possui uma entrada de tamanho n.

– Opera de modo determinístico em tempo polinomial p(n).

– Produz uma saída uma fita separada, denominada fita de saída.

● O tamanho da saída e no máximo p(n).

Tradutor de tempo polinomial

estado

nentrada

Fitas de rascunho

Fita desaída

< p(n)

Lembre-se: requerimento importanteé tempo < p(n).

Redução de tempo polinomial● Considere L e M linguagens.● Digamos que L seja redutível em tempo

polinomial a M se existe um tradutor T tal que para toda entrada w de T, a saída x = T(w) pertence a M se e somente se w pertence a L.

Redução de tempo polinomial

T

w ∈ L

w ∉ L

x ∈ M

x ∉ M

Problemas NP-completos

● Um problema/linguagem M é dito NP-completo se para toda linguagem L em NP, há uma redução de tempo polinomial de L para M.

● Propriedade fundamental: Se L é redutível a M em tempo polinomial e M possui um algoritmo de tempo polinomial, então L também tem um algoritmo de tempo polinomial.

Problemas NP-completos

R

S

sim

não

Tradutorx

w

- Tradutor executa em tempo p(n) (polinômio)- R decide em tempo q(n) (polinômio)- S decide em tempo p(n) + q(n) (polinômio)- M = L(R)- L = L(S)

Problemas NP-completos

Redução de tempo polinomial

NP

Um problemaNP-completo

.

. . .

.

..

. Um problema NP

. .

O plano

NP

SAT

Todos os problemas NPse reduzem em tempo polinomialao SAT, que é NP-completo

3-SAT

SAT se reduz emtempo polinomialao 3-SAT

3-SAT se reduz em tempopolinomial a muitos problemasque também são NP-completos

Prova que Reduções polinomiais funcionam● Suponha que M possui um algoritmo de

tempo polinomial q(n).● Considere que L tenha uma tradutor T

para M que leva uma tempo polinomial p(n).

● O tempo do algoritmo para M junto ao tempo de produção da saída de T leva no máximo q(p(n)).

Prova que Reduções polinomiais funcionam● Agora possuímos um algoritmo para L em

tempo polinomial.– Dada uma entrada w de tamanho n, use T para

produzir x de tamanho < p(n), usando um tempo menor que p(n).

– Use o algoritmo para M informar se x pertence a M em tempo < q(p(n)).

– Responda se w pertence L caso x pertença M.

● Tempo total < p(n) + q(p(n)) = um polinômio.

Próxima aula

● Veremos o problema SAT e porque ele é NP-completo.

NP-completude e heurísticas● Na vida prática, quando encontramos

problemas que são comprovadamente NP-completos, devemos:– Descobrir ou desenvolver heurísticas.

– Reduzir o conjunto de entradas para adequar a realidade do problema real.

Referências

● HOPCROFT, John E.; ULLMAN, Jeffrey D.; MOTWANI, Rajeev. Introdução à teoria de autômatos, linguagens e computação. [Rio de Janeiro]: Campus, c2003. p. 328-352

● SIPSER, Michael. Introdução à teoria da computação. 2ª Ed. Thomson. São Paulo. 2007.

● Traduzido e adaptado dos slides de Jeffrey D. Ullman.