Navigation

Problemas de Decisão

Para o estudo das classes de complexidade, é conveniente considerar apenas os problemas de decisão. Como será visto a seguir, todo problema de otimização pode, para fins de classificação quanto à complexidade, ser transformado em um problema de decisão. Ainda nesta seção, será observado que vários problemas de decisão são "fáceis". A seguinte convenção é adotada: se $\Pi$ é um problema, então $\Pi$ também identifica o seu conjunto de instâncias. Nesse sentido, as instâncias podem ser particionadas na forma $\Pi = \Pi_{sim} \cup \Pi_{n\tilde{a}o}$, sendo $\Pi_{sim}$ e $\Pi_{n\tilde{a}o}$ os conjuntos de instâncias cujas respostas são "sim" e "não", respectivamente.

Alguns exemplos de problemas de decisão envolvem fórmulas lógicas. Para definir esses problemas, diz-se que uma fórmula lógica está na forma normal conjuntiva, ou FNC, se:

  1. ela é formada por literais, conectivos $\vee$ e $\wedge$, e parênteses. Um literal é uma variável lógica (cujos valores podem ser $\mathbf{V}$ ou $\mathbf{F}$) ou sua negação.
  2. ela está escrita como um $\wedge$ ("E" lógico) de cláusulas. Uma cláusula é um $\vee$ ("OU" lógico) de literais.

Se $x_1, x_2, x_3, x_4$ são variáveis lógicas, então a fórmula

$(x_1 \vee \bar{x}_2 \vee x_4) \wedge x_2 \wedge (\bar{x}_3 \vee \bar{x}_4)$

está na FNC. O primeiro problema de decisão envolvendo fórmulas lógicas é o seguinte.

SATISFABILIDADE (SAT)

ENTRADA: fórmula lógica $f(x_1, x_2, \cdots, x_\ell)$ na FNC
QUESTÃO: existe uma atribuição (de $\mathbf{V}$ ou $\mathbf{F}$) às variáveis $x_1, x_2, \ldots, x_\ell$ tal que $f(x_1, x_2, \ldots, x_\ell) = \mathbf{V}$ ?


As fórmulas na FNC em que as cláusulas possuem todas o mesmo número de literais distintos merecem atenção especial. As fórmulas que têm esse número de literais igual a $k$ são ditas estar na $k$-FNC. A versão de SAT para na qual a fórmula está na $k$-FNC é conhecida por $k$-SAT.

$k$-SATISFABILIDADE ($k$-SAT)

ENTRADA: fórmula lógica $f(x_1, x_2, \cdots, x_\ell)$ na $k$-FNC, para algum $k$ fixo
QUESTÃO: existe uma atribuição (de $\mathbf{V}$ ou $\mathbf{F}$) às variáveis $x_1, x_2, \ldots, x_\ell$ tal que $f(x_1, x_2, \ldots, x_\ell) = \mathbf{V}$ ?


A restrição aos problemas de decisão não impede que também possamos classificar os problemas de otimização. Para melhor visualizar essa última afirmação, vamos observar como obter uma versão de decisão do problema da mochila.

MOCHILA

ENTRADA: número de objetos $n$, $n > 0$, pesos $w_1, w_2, \cdots, w_n$, valores $v_1, v_2, \cdots, v_n$, capacidade da mochila $W$, $W < \sum_{i = 1}^n w_i$, inteiro $K > 0$.
QUESTÃO: Existe $N' \subset N$ tal que $\sum_{i \in N'} w_i \leq W$ e $\sum_{i \in N'} v_i \geq K$ ?


Note que a versão de decisão é obtida estabelendo um valor mínimo $k$ para a função de custo que deve ser maximizada na versão de otimização, sendo que a pergunta da versão de decisão passa ser se existe alguma solução cujo custo não é inferior a esse valor mínimo. Desta mesma forma podemos obter uma versão de decisão para todo problema de maximização.

De maneira equivalente, podemos chegar a uma versão de decisão de um problema de minimização. Tomando como exemplo o problema da coloração de vértices, chegamos a seguinte versão de decisão.

COR

ENTRADA: grafo $G = (N, A)$, inteiro $k > 0$
QUESTÃO: Existe uma $k$-coloração de $G$ ?


Desta vez, tratando-se de um problema de minimização, é estabelecido um valor máximo $k$, e indaga-se a existência de uma solução de custo no máximo $k$.

Ao classificarmos apenas os problemas de decisão "difíceis", estamos também classificando os problemas de otimização "difíceis". Se a versão de decisão de um problema de otimização é classificado como difícil, então o próprio problema de otimização também o é. Basta observar que uma solução do problema de otimização permite a solução da versão de decisão. Portanto, a versão de decisão não mais "difícil" que o problema de otimização.

Definição da Classe $P$

Voltando à questão da definição dos problemas "fáceis", eles são incluídos na seguinte classe:

$P = \left\{ \Pi \mid \Pi \mbox{ é um problema de decisão para o qual existe um algoritmo polinomial } \right\}$

Um exemplo de problema em $P$ é o seguinte:

COLORAÇÃO GRAFO DE INTERVALO

ENTRADA: conjunto $\mathcal I$ de intervalos em $\mathbb{R}$, inteiro $k > 0$
QUESTÃO: Existe uma $k$-coloração do grafo de intervalos associado a $\mathcal I$ ?


Esse problema corresponde à versão de decisão do problema de coloração de grafos de intervalos. Visto que existe um algoritmo de complexidade $O(n^2)$ ($n$ é o número de intervalos) para a versão de otimização, a versão de decisão pertence a $P$.

Um segundo exemplo de problema em $P$ é o seguinte:

EMPARELHA

ENTRADA: grafo bipartido $G$
QUESTÃO: Existe um emparelhamento perfeito em $G$ ?


A partir de algoritmos polinomiais para um problema em $P$, podemos demonstrar a existência de outros problemas em $P$. Um exemplo é 2-SAT, pois resolver uma instância desse problema corresponde a realizar um percurso em determinado grafo direcionado, construído a partir das variáveis e cláusulas da instância de 2-SAT.