Problemas de decisão, P e NP

Há muitos problemas de computação com aplicações práticas importantes para os quais não conhecemos algoritmos eficientes como, por exemplo, o Problema de roteamento de veículos. Se por um lado, nesses casos, o computador se torna inútil para instâncias grandes, por outro lado, a existência de problemas (possivelmente) difíceis de se resolver computacionalmente é a base das operações primitivas da Criptografia. A Complexidade Computacional é a disciplina que se ocupa de classificar os problemas computacionais de acordo com a dificuldade computacional intrínseca dos problemas.

Lembremos que um problema computacional abstrato é caracterizado por uma tripla {(\mathcal I, \mathcal O, \mathcal R)} onde {\mathcal I} denota o conjunto das instâncias do problema, {\mathcal O} é o conjunto das respostas e {\mathcal R \subset \mathcal I\times \mathcal O} é uma relação que associa a cada instância uma ou mais respostas. Uma solução computacional é um dispositivo de computação que computa uma função {A\subset \mathcal R}; nesse caso dizemos que {A} é uma função computável. Quando consideramos as codificações das instâncias e das respostas de um problema computacional abstrato sobre um alfabeto finito temos um problema computacional concreto. No que segue, não distinguimos os problemas entre concreto e abstrato e esperamos que esteja claro no contexto a qual nos referimos.

Os problema computacionais podem ser classificados em problemas de decisão, por exemplo,

Dado um grafo {G}, determinar se {G} é conexo

problemas de busca, por exemplo,

Dado um grafo {G}, determinar as componentes conexas de {G}

os problemas de otimização, por exemplo,

Dado um grafo {G}, determinar o tamanho do maior conjunto independente {G}

Embora a classificação seja natural, todo problema pode ser formulado como um problema de busca. Num problema de busca a cada instância {x} está associado um conjunto {R(x)=\{y:(x,y)\in \mathcal R\}} das soluções possíveis, que pode ser vazio. Uma solução do problema é uma função computável {A} tal que {A(x) \in R(x)} sempre que {R(x) \neq \emptyset}, caso contrário {A(x) := \emptyset}. Os problemas de otimização podem ser formulados como problema de busca se consideramos que cada resposta {(x,y)} tem um custo {f(x,y)} e buscamos pelas respostas que excedem um limiar ou atingem um valor máximo. No primeiro caso, dado {(x,v)} procuramos por {y\in R(x)} tal que {f(x,y) \geq v} e no segundo caso, buscamos por {y} tal que {f(x,y)\leq k}, dentre todos {y\in R(x)}.

— Problemas de decisão —

Nos restringiremos ao estudo dos problemas computacionais de decisão. Embora isso seja restritivo, fazemos isso seguindo uma tradição na área porque a apresentação e a formalização são mais simples. Ademais, mostramos abaixo que essa não é uma restrição tão severa com aparenta pois, em geral, um algoritmo eficiente para uma versão de decisão de um problema de busca implica num algoritmo eficiente para o problema de busca.

Num problema de decisão

\displaystyle \mathcal O = \{\mathrm{sim},\mathrm{n\tilde{a}o}\}

e, usualmente, especificamos um subconjunto {L \subset \mathcal I} tal que {A(x) = \text{sim}} se e somente se {x\in L}; desse modo o problema é decidir se uma instância qualquer {x} pertence ao conjunto {L}. Por exemplo, decidir se um número é primo tem {\mathcal I} como o conjunto dos inteiros positivos e {L} o subconjunto dos inteiros positivos e primos; o teste em si é uma função computável {A} que responde sim se {x} pertence a {L}, caso contrário responde não, isto é, decide se {x} é ou não é um número primo.

Quando consideremos a codificação das instâncias chamamos {L} de linguagem sobre o alfabeto {\Sigma}

\displaystyle L = \{ \langle x \rangle : x\in \mathcal I \text{ e } (x,\mathrm{sim})\in \mathcal R\}

Exemplo 1 (sat) O problema {\textsc{sat}} é o problema de decidir se uma fórmula booleana é satisfazível. Nesse caso, {\mathcal I} é a família de todas as fórmulas booleanas, {\mathcal O = \{\mathrm{sim},\mathrm{n\tilde{a}o}\}} e a relação {\mathcal R} é dada pelos pares {(\Phi, \mathrm{sim})} e {(\Phi',\mathrm{n\tilde{a}o})} para cada {\Phi\in\mathcal I} satisfazível e cada {\Phi'\in\mathcal I} não satisfazível.

Uma fórmula booleana {\Phi}=(X,C) é dada pelo conjuntos {X=\{x_1,\dots,x_m\}} de suas variáveis é {C=\{C_1,\dots,C_k\}} de suas cláusulas. Uma cláusula é uma disjunção de literais

\displaystyle C_i = l_{i_1} \vee l_{i_2} \vee \cdots \vee l_{i_p}

e um literal é uma variável ou a negação dela; {\Phi = C_1 \wedge \cdots \wedge C_k}. Uma atribuição é uma função {t : X \rightarrow \{\mathrm{verdadeiro},\mathrm{falso}\}} que atribui os valores verdadeiro ou falso a cada uma das variáveis e uma fórmula é satisfazível quando existe uma atribuição que torne a fórmula verdadeira.

A linguagem {\textsc{sat}} é dada por

\displaystyle \textsc{sat} := \bigg\{\langle X,C \rangle : C_1 \wedge \cdots \wedge C_k \text{ \'e verdadeira para alguma atribui\c c\~ao }t \bigg\}

em que {C_i} são cláusulas.

Notemos que caso exista uma valoração que satisfaça a fórmula, a princípio não é preciso determinar de fato a valoração para decidir que a fórmula é satisfazível.

A versão de busca do problema {\textsc{sat}} pede para determinar uma valoração {t} das variáveis de {\Phi} que torne a fórmula verdadeira ou determinar que tal valoração não existe. Se {\Phi = \Phi(x_1,x_2,\dots,x_m)} e existe um algoritmo {A} para {\textsc{sat}} de tempo {T_\textsc{s}(n)} então, caso {\Phi} seja satisfazível, podemos determinar uma valoração da seguinte maneira: usamos {A} para decidir se {\Phi(1,x_2,\dots,x_m)} é satisfazível, se não for satisfazível então {\Phi(0,x_2,\dots,x_m)} é satisfazível; determinado o valor de {x_1}, repetimos o processo para determinar o valor de {x_2}, e assim por diante. Tal algoritmo tem tempo

\displaystyle 2m\cdot T_\textsc{s}(n) = O(nT_\textsc{s}(n)) \ \ \ \ \ (1)

Exemplo 2 (circuito hamiltoniano) O problema do circuito hamiltoniano é decidir se um grafo {G} possui um circuito que contém todos os vértices do grafo. Um grafo {G} é dado por par de conjuntos {(V,A)} de modo que {V} é um conjunto finito cujos elementos são chamados de vértice e de modo que cada elemento de {A}, chamado de aresta, é dado por dois elementos de {V}. Assumiremos que {V=\{1,2,\dots,N\}} para algum natural {N}.

Um circuito hamiltoniano é uma permutação {(v_1,v_2,\dots,v_n)} dos vértices de modo que {\{v_1,v_n\},\{v_i,v_{i+1}\}\in A}, {(i\in \{1,\dots,n-1\})}.

A linguagem {\textsc{hamiltoniano}} é

\displaystyle \textsc{hamiltoniano}:= \big\{ \langle G \rangle : G \text{ \'e hamiltoniano} \big\}.

A versão de busca desse problema de decisão é: dado um grafo {G}, determinar um circuito hamiltoniano em {G} caso exista. Como no caso do {\textsc{sat}}, suponhamos a existência de um algoritmo {A} que em tempo {T_\textsc{h}(n)} decide {\textsc{hamiltoniano}}, onde {n} é o tamanho do grafo (usando matriz de adjacências {n=N^2}). Esse algoritmo pode ser usado para determinar um circuito quando existe: se {A(G) = \mathrm{n\tilde{a}o}} então não há o que fazer; senão, para cada {a\in A} fazemos: se {A(G-a)=\mathrm{sim}} então {A \gets A -\{a\}}. Percorra o grafo resultante e devolva a sequência dos vértices visitados no percurso. Tal percurso pode ser uma busca em profundidade cujo custo é linear em {n}. Esse algoritmo determina um circuito quando existe em tempo no máximo

\displaystyle |A|\cdot T_\textsc{h}(n) + O(n) = O(nT_\textsc{h}(n)). \ \ \ \ \ (2)

 

Exemplo 3 (caixeiro viajante) O problema do caixeiro viajante é: dado um grafo {G=(V,A)} com {\rho : A \rightarrow {\mathbb Z}^+} pesos positivos nas arestas determinar, caso exista, um circuito hamiltoniano de peso mínimo. O peso de um circuito é a soma dos pesos de suas arestas.

Esse problema não é de decisão e sua versão de decisão é descrita como: dado um grafo {G=(V,A)} com {\rho : A \rightarrow {\mathbb Z}^+} pesos positivos nas arestas e dado {k\in {\mathbb Z}^+} decidir se {G} possui um circuito hamiltoniano de peso {\leq k}. A linguagem {\textsc{tsp}} é

\displaystyle \textsc{tsp}:= \big\{ \langle G,k \rangle : G \text{ tem circuito hamiltoniano de peso }\leq k \big\}.

Exercício 1 Suponha a existência de um algoritmo que em tempo {T_\textsc{t}(n)} decide {\textsc{tsp}}. Exiba um algoritmo de tempo

\displaystyle O(\log(|A|n) \cdot T_\textsc{t}(n)) \ \ \ \ \ (3)

 

que usa essa solução de {\textsc{tsp}} e determina o peso de um circuito hamiltoniano de peso mínimo. (Note que { O(\log(|A|n) \cdot T_\textsc{t}(n)) = O(\log(n) \cdot T_\textsc{t}(n))})

Exercício 2 Dê, um função dos resultados obtidos no exercício anterior, um algoritmo que determina uma solução para o problema do caixeiro viajante e estipule a complexidade de tempo do seu algoritmo.

— Algoritmos eficientes —

Dizemos que um algoritmo tem complexidade polinomial se o consumo de tempo no pior caso para as entradas de tamanho {n} é {T(n)=O(n^k)} para alguma constante inteira e positiva {k}. Para simplificar dizemos, de modo genérico, algoritmo de tempo polinomial.

Tradicionalmente, computação eficiente é sinônimo de computação feita por um dispositivo com complexidade polinomial.

Notemos que a classe das funções polinomiais é fechada para soma, multiplicação e composição, o que é bastante apropriado do ponto de vista teórico pois a noção de eficiência é preservada por práticas comuns de programação. Além disso, os modelos tradicionais de computação são polinomialmente equivalentes o que torna a escolha do modelo irrelevante para essa definição de eficiência. Além disso, com algum cuidado, as várias representações computacionais de objetos abstratos, como um grafo por exemplo, têm tamanhos polinomialmente relacionados, o que faz a codificação ser irrelevante.

Notemos que no caso dos exemplos 1, 2 e 3 obtemos das equações (1) e (2) e dos exercícios 1 e 2 que se os problemas de decisão têm algoritmo eficiente então os respectivo problemas de busca também têm algoritmo eficiente.

— Classes de complexidade —

Uma classe de complexidade computacional, com respeito a um modelo de computação e um tipo de problema, é o conjunto dos problemas que são resolvidos por um dispositivo computacional naquele modelo com alguma restrição de recurso como o tempo, por exemplo. Como nos restringimos aos problemas de decisão, as classes de complexidade são apresentadas como classe de linguagens ao invés de classe de problemas.

A classe {\mathtt{P}}Polynomial time — é a classe das linguagens decididas por algoritmos de tempo polinomial. Por exemplo, o problema de decidir se um inteiro positivo é primo está em {\mathtt{P}}. Não sabemos se {\textsc{sat} \in \mathtt{P}} pois não conhecemos nenhum algoritmo de tempo polinomial para {\textsc{sat}} e não sabemos sequer se tal algoritmo pode existir.

Um verificador de tempo polinomial para uma linguagem {L} é um algoritmo de tempo polinomial {M} tal que para todo {w\in \{0,1\}^*}

  • se {w\in L} então existe {c\in\{0,1\}^{p(|w|)}} tal que {M(w,c)=1}, para algum polinômio {p} e
  • se {w\not\in L} então {M(w,c)=0} para todo {c\in\{0,1\}^* }.

Uma sequência {c} como acima é chamada de certificado ou testemunha. Se {w\in L} então há um certificado curto, de tamanho polinomial em {|w|}, que convence o verificador de tal fato, senão, caso {w\not\in L}, não há tal certificado que convença o verificador do contrário.

A classe {\mathtt{NP}}Nondeterministic Polynomial time — é a classe das linguagens que admitem um verificador de tempo polinomial.

Proposição 1 {\textsc{hamiltoniano}\in\mathtt{NP}}

Demonstração: Para cada grafo {G \in \textsc{hamiltoniano}} temos que o circuito hamiltoniano dado por uma permutação {C=(v_1,v_2,\dots,v_n)} é um certificado pois {|\langle C\rangle| \leq |\langle G\rangle|} e podemos verificar em tempo linear se {C} é um circuito em {G}. \Box

A linguagem {\textsc{composto}} é dada pelos números inteiros, positivos e compostos.

Proposição 2 {\textsc{composto} \in\mathtt{NP}}

Demonstração: De fato, dado um inteiro positivo {n}, um certificado para {n\in \textsc{composto}} é um inteiro {q}, {1<q<n}, divisor de {n}. Claramente, {|\langle q\rangle| \leq |\langle n\rangle|} e podemos testar em tempo polinomial em {\log n} se {q} divide {n}. \Box

Proposição 3 {\textsc{sat}\in\mathtt{NP}}.

Demonstração: Para cada fórmula satisfazível {\Phi=(X,C)} existe uma valoração {t} das variáveis de {X} que torna a fórmula verdadeira. Claramente o tamanho {|\langle t \rangle| = O(|X|)} é linear em {|\langle X,C \rangle|}. Ademais, é simples escrever um verificador que recebe {\Phi} e {t} que verifica em tempo polinomial se a valoração {t} das variáveis de {\Phi} a torna verdadeira. \Box

Teorema 4 {\mathtt{P} \subset \mathtt{NP}}.

Demonstração: Se {L\in \mathtt{P}} então existe um algoritmo eficiente {M} que decide {L}.

Um verificador {V} para {L} é o algoritmo {V(w,c) := M(w)} que, obviamente, é eficiente, portanto {L\in\mathtt{NP}}. \Box

Não é sabido se a inclusão {\mathtt{NP}\subset \mathtt{P}} é verdadeira. Esse é um dos principais, senão o principal, problema não resolvido da Teoria da Computação e foi formulado independentemente por Stephen Cook e Leonid Levin em 1971

{\mathtt{P}\neq \mathtt{NP}}?

— Complementos —

Notemos que a definição de {\mathtt{NP}} é assimétrica. Consideremos a linguagem \textsc{não-hamiltoniano} formada pelo grafos que não são hamiltonianos. Não conhecemos nenhum certificado de tamanho polinomial que certifique que um grafo não é hamiltoniano, ou seja, não sabemos se {\textsc{nao-hamiltoniano}\in \mathtt{NP}}.

Se {\mathtt{C}} é uma classe de complexidade e {L} uma linguagem então {L\in \mathtt{coC}} se, e somente se, o complemento de {L}, denotado {\overline L}, está em {\mathtt{C}}. Pode-se deduzir facilmente da definição que {\mathtt{P}= \mathtt{coP}}: se {L\in \mathtt{P}} então existe um algoritmo polinomial {M} que decide {L}. O algoritmo {\overline M(w) := 1- M(w)} de tempo polinomial decide {\overline{L}}, portanto {L \in \mathtt{coP}}. A recíproca desses argumentos valem, ou seja, {\mathtt{coP} \subset \mathtt{P}}, portanto esses conjuntos são iguais. No entanto, na definição de {\mathtt{NP}} há uma assimetria entre aceitar e rejeitar uma palavra o que invalida o mesmo argumento para tentar provar que {\mathtt{NP} = \mathtt{coNP}}. De fato, atualmente, não é sabido se vale tal igualdade.

{\mathtt{NP} \neq \mathtt{coNP}}?

Uma definição alternativa é: {L\in\mathtt{coNP}} se exite um polinômio {p} e uma verificador {V} tais que

\displaystyle x\in L \Leftrightarrow \text{para todo }c\in \{0,1\}^{p(|x|)},~V(x,c)=1.

Por exemplo, a linguagem \textsc{taut} formada pelas fórmulas booleanas verdadeiras, isto é, que são satisfeitas por qualquer valoração está em {\mathtt{coNP}}.

Exercício 3 Mostre que se {\mathtt{P}=\mathtt{NP}} então {\mathtt{NP}=\mathtt{coNP}}.

Exercício 4 Mostre que {\mathtt{P} \subset \mathtt{NP}\cap\mathtt{coNP}} então {\mathtt{NP}=\mathtt{coNP}}.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s