Complexidade computacional

Numa mochila, verificar uma seleção proposta exige somar os pesos e os valores e compará-los com os limites. Encontrar essa seleção pode exigir muito mais trabalho do que a verificação. A teoria da complexidade distingue problemas que sabemos resolver em tempo polinomial dos que admitem respostas verificáveis nesse tempo.

A versão do problema, a representação dos números e a direção de uma redução fazem parte da análise. Um certificado curto não demonstra que sabemos encontrar a resposta rapidamente, apenas que sabemos reconhecê-la quando a vemos.

Decisão, certificados e classes

Um problema de decisão responde sim ou não. Na mochila, “há uma seleção de peso no máximo $W$ e valor pelo menos $K$?” é decisão; “qual é o maior valor?” é otimização.

P contém problemas de decisão resolvidos em tempo polinomial no tamanho da representação da entrada. NP contém os que admitem um certificado de tamanho polinomial verificável em tempo polinomial. Para uma mochila, o certificado é a lista de objetos; somar pesos e valores e comparar os limites verifica-o.

$P\subseteq NP$, pois podemos ignorar o certificado e resolver. Não sabemos se $P=NP$. NP não significa “não polinomial”, porque há problemas em NP que pertencem a P.

Um problema é NP-difícil se todo o problema de NP se reduz a ele em tempo polinomial. É NP-completo se também pertence a NP. A definição de NP-completo aplica-se a decisão; a versão de otimização correspondente costuma ser descrita como NP-difícil.

co-NP contém os complementos dos problemas de NP. Uma fórmula não ser uma tautologia tem um certificado curto: uma atribuição que a torna falsa. Por isso TAUTOLOGY pertence a co-NP. Isto não prova que pertence ou não pertence a NP.

Problemas indecidíveis, como parar ou não para programas gerais, são outra questão: não há algoritmo que resolva todas as entradas. NP-completude trata problemas decidíveis e o tempo necessário para os resolver.

Direção de uma redução

Escrevemos $A\le_p B$ quando há uma transformação polinomial $f$ tal que

$$x\in A\iff f(x)\in B.$$

Se soubéssemos resolver $B$, resolveríamos $A$ transformando a entrada e chamando esse algoritmo. Para provar que um novo problema $B$ é difícil, reduzimos um problema difícil conhecido para $B$. Mostrar $B\le_p A$ só mostra que $B$ não é mais difícil que $A$ segundo essa transformação.

Uma prova precisa da construção, do tamanho/custo e das duas implicações. Enumerar $2^n$ atribuições para produzir uma transformação não é uma redução polinomial, mesmo que a expressão final pareça simples, porque a enumeração já custa exponencial.

De circuitos para fórmulas

CIRCUIT-SAT é um problema NP-completo conhecido: pergunta se algum valor das entradas de um circuito booleano faz a saída verdadeira. Este resultado de base permite iniciar a cadeia de reduções. Introduz uma variável para cada fio e restrições que representam cada porta. Para $z=x\land y$, usa

$$(\neg z\lor x)\land(\neg z\lor y)\land(z\lor\neg x\lor\neg y).$$

As cláusulas dizem que $z$ verdadeiro exige as duas entradas verdadeiras e que ambas verdadeiras exigem $z$ verdadeiro. Acrescenta a cláusula que impõe a saída. Há um número constante de cláusulas por porta, portanto o tamanho cresce linearmente com o circuito. Não precisamos de expandir uma tabela de verdade para todas as entradas.

Para uma cláusula longa de cinco literais, introduz auxiliares:

$$(\ell_1\lor\ell_2\lor y_1)\land(\neg y_1\lor\ell_3\lor y_2)\land(\neg y_2\lor\ell_4\lor\ell_5).$$

Ela é satisfazível para alguma escolha de $y_1,y_2$ exatamente quando a cláusula original é verdadeira. A transformação preserva satisfazibilidade, não a equivalência para todas as atribuições das variáveis novas. A generalização acrescenta um número linear de cláusulas e transforma CNF-SAT em 3-CNF-SAT. Uma cláusula com um ou dois literais pode repetir literais até ter três posições, sem mudar a condição de verdade.

De satisfazibilidade para clique

Uma clique de tamanho $k$ é um conjunto de $k$ vértices em que cada par tem uma aresta. Para uma fórmula CNF com $q$ cláusulas, cria um vértice por ocorrência de literal. Liga dois vértices se vêm de cláusulas diferentes e os literais não são contraditórios. Pede clique de tamanho $q$.

Se a fórmula é satisfazível, escolhe em cada cláusula um literal verdadeiro. Esses $q$ vértices são compatíveis dois a dois e formam uma clique. Reciprocamente, uma clique de tamanho $q$ escolhe exatamente um literal de cada cláusula, pois não há arestas dentro da mesma. Não escolhe um literal e a sua negação; podemos torná-los todos verdadeiros e satisfazer as cláusulas.

Por exemplo, $(x\lor y)\land(\neg x\lor z)\land(\neg y\lor z)$ admite escolher as ocorrências $x,z,z$. As duas ocorrências de $z$ são vértices diferentes, de cláusulas diferentes, e podem estar ligadas. Não fundas ocorrências só porque têm o mesmo texto.

Com $r$ ocorrências, há $r$ vértices e no máximo $O(r^2)$ arestas. O certificado de clique lista $q$ vértices e é verificável em tempo polinomial. A redução dá a dificuldade; a verificação dá a pertença a NP.

De clique para cobertura de vértices

Uma cobertura de vértices contém pelo menos um extremo de cada aresta. Um conjunto independente não tem arestas entre os seus vértices. $C$ é cobertura de $G$ se e só se $V\setminus C$ é independente em $G$.

Uma clique de tamanho $k$ em $G$ é independente de tamanho $k$ no complemento $\overline G$. Logo existe clique de tamanho $k$ em $G$ se e só se existe cobertura de tamanho no máximo $n-k$ em $\overline G$. O complemento liga exatamente os pares distintos que não estavam ligados em $G$. A construção custa $O(n^2)$.

A direção e o complemento são decisivos. Procurar diretamente uma cobertura de $G$ de tamanho $n-k$ corresponderia a um conjunto independente de $G$, não a uma clique.

De 3-SAT para três cores

3-COLORABILITY pergunta se um grafo não dirigido admite uma coloração com no máximo três cores. Uma lista de cores verifica-se em $O(n+m)$: confirma a cor de cada vértice e que cada aresta tem extremos diferentes. O problema pertence, portanto, a NP. Para provar a dificuldade, transformamos uma fórmula 3-SAT num grafo.

Cria primeiro um triângulo com vértices $T,F,B$. Os três precisam de cores distintas, às quais damos esses mesmos nomes. Para cada variável $x$, cria vértices $x$ e $\neg x$, liga-os entre si e liga ambos a $B$. Só podem ter as cores $T$ e $F$, em sentidos opostos, representando uma atribuição booleana.

Para cada cláusula $(\ell_1\lor\ell_2\lor\ell_3)$, acrescenta seis vértices novos $O_1,O_2,O_3,I_1,I_2,I_3$ e estas arestas:

Ligações	Restrição que impõem
$I_1I_2$, $I_2I_3$, $I_3I_1$	O triângulo interno usa as três cores
$I_iO_i$, para $i=1,2,3$	Cada interno difere do externo correspondente
$O_iT$ e $O_i\ell_i$, para $i=1,2,3$	Cada externo difere de $T$ e do seu literal

Nesta construção, os externos ligam-se ao vértice $T$. Fixar este nome evita trocar o papel das cores na prova.

Se os três literais forem falsos, cada $O_i$ é adjacente a $T$ e $F$, logo fica forçado a $B$. Nenhum $I_i$ pode então usar $B$, e um triângulo não admite apenas duas cores, por isso a cláusula falsa impede colorir o grafo.

Se algum literal, por exemplo $\ell_1$, for verdadeiro, dá $F$ a $O_1$ e $B$ aos outros dois externos. São escolhas válidas, mesmo que os outros literais também sejam verdadeiros. Dá $B$ a $I_1$ e $T,F$ aos dois restantes. Todas as arestas têm cores diferentes nos extremos. Qualquer cláusula verdadeira pode, assim, ser completada.

Uma atribuição que satisfaz a fórmula colore os vértices das variáveis e completa cada cláusula. Reciprocamente, qualquer coloração define uma atribuição, e nenhuma cláusula pode ter todos os literais falsos. Temos as duas implicações da redução. Com $v$ variáveis e $q$ cláusulas, há $3+2v+6q$ vértices e $O(v+q)$ arestas; a construção é linear. Assim, 3-COLORABILITY é NP-completo.

O número cromático $\chi(G)$ é o menor número de cores de uma coloração válida. Uma clique de tamanho $k$ exige $k$ cores. Se $\Delta(G)$ é o maior grau, colorir sequencialmente com uma cor livre usa no máximo $\Delta(G)+1$ cores num grafo simples, pois cada vértice tem no máximo $\Delta(G)$ vizinhos. Isso é um limite superior, não uma garantia de mínimo. Num triângulo, $\chi=3$ e $\Delta=2$: nem sequer $\Delta$ cores chegam sempre.

Um caso que fica em P: 2-SAT

Para cada variável cria os vértices $x$ e $\neg x$. Uma cláusula $(a\lor b)$ equivale a $\neg a\Rightarrow b$ e $\neg b\Rightarrow a$; acrescenta essas duas arestas.

A fórmula é insatisfazível se alguma variável e a sua negação estiverem na mesma SCC. Nesse caso, escolher qualquer valor força o outro por implicações. Se nenhuma coincide, a condensação é um DAG e podemos escolher valores segundo uma ordem das componentes, dando a cada literal o valor complementar da sua negação. A regra concreta de comparação depende de como numeramos as componentes; verifica-a contra a ordem topológica usada.

Para uma regra independente da numeração das SCC, escolhe uma ordem topológica da condensação e dá a cada componente a sua posição crescente. Atribui $x$ a verdadeiro se a componente de $x$ estiver depois da de $\neg x$. Cada variável e a sua negação recebem valores opostos.

Esta regra respeita as implicações. Suponhamos que $a\Rightarrow b$ tem $a$ verdadeiro e $b$ falso. Há também a aresta $\neg b\Rightarrow\neg a$, pois cada cláusula acrescenta as duas. As posições teriam de satisfazer

$$\operatorname{pos}(\neg a)<\operatorname{pos}(a)\le\operatorname{pos}(b)<\operatorname{pos}(\neg b)\le\operatorname{pos}(\neg a),$$

o que é impossível. Logo nenhuma cláusula fica falsa. Numa cláusula unitária $(x)$, vista como $(x\lor x)$, a aresta $\neg x\to x$ coloca $x$ depois da sua negação e atribui-lhe verdadeiro, como esperado.

O grafo tem $2n$ vértices e $2q$ arestas para $q$ cláusulas, e as SCC dão decisão em $O(n+q)$. 2-SAT está em P; 3-SAT é NP-completo. Isto não prova uma separação entre as classes, porque continua em aberto se $P=NP$.

Autorredução: do decisor à solução

Um decisor responde sim ou não; um construtor devolve o objeto. Para a mochila de decisão com limite $K$, cada pergunta ao decisor fixa um objeto como dentro ou fora e ajusta capacidade e limite: perguntar com o objeto $i$ incluído equivale a decidir $(W-w_i,K-v_i)$ no resto; excluído equivale a $(W,K)$. Conserva a escolha que mantém a resposta afirmativa. Com $n$ chamadas, recupera a seleção sem enumerar subconjuntos.

Para HAM-CYCLE, usa apenas o decisor comum que recebe um grafo. Se $G$ tem ciclo hamiltoniano, percorre as arestas por ordem: para cada aresta $e$, pergunta se $G-e$ ainda tem ciclo hamiltoniano. Se sim, remove $e$ em definitivo; se não, conserva $e$. O invariante é que o grafo corrente continua hamiltoniano. No fim, nenhuma aresta pode sair sem destruir essa propriedade, e um grafo hamiltoniano minimal com $n$ vértices é exatamente um ciclo de $n$ arestas. Se o decisor for polinomial, a construção com $m$ chamadas também é.

Certificados e instâncias especiais

Para dois grafos simples não dirigidos, um certificado de isomorfismo é uma bijeção $\pi$ entre os vértices. Verifica primeiro que cada imagem é válida e ocorre uma só vez. Depois, para cada par distinto $u,v$, exige

$$uv\in E(G)\iff\pi(u)\pi(v)\in E(H).$$

A equivalência exclui também arestas extra em $H$. Com matrizes de adjacência, há $O(n^2)$ pares a comparar. A lista da bijeção ocupa $O(n\log(n+1))$ bits e o verificador é polinomial. Isto situa isomorfismo em NP; não prova pertença a P nem NP-completude.

PARTITION pergunta se um multiconjunto de inteiros positivos pode ser dividido em partes de igual soma. Para transportar a dificuldade de SUBSET-SUM, recebe A e alvo inteiro $T\ge0$, calcula $s=\sum A$ e acrescenta $b=|s-2T|$ quando $b>0$. A nova metade é $(s+b)/2$.

• Se $s>2T$, a metade é $s-T$. Um subconjunto de soma T, junto com b=s-2T, atinge essa metade. Inversamente, retirar b do lado que o contém deixa soma T.
• Se $s<2T$, a metade é T. O subconjunto original de soma T forma um lado; o seu complemento junto com b=2T-s forma o outro. Inversamente, o lado que não contém b é um subconjunto de A com soma T.
• Se $s=2T$, nada se acrescenta: a instância original já pede partes com soma T.

Por exemplo, A=[3,1,4,2,2] tem soma 12. Para T=3, acrescentamos 6 e obtemos partes [3,6] e [1,4,2,2], ambas de soma 9. Para T=6, nada se acrescenta e [3,1,2] e [4,2] já dão uma partição.

A construção usa somas e um novo inteiro de comprimento polinomial na entrada. Um certificado marca as ocorrências de cada parte e verifica as duas somas em tempo polinomial nos bits. Com a NP-completude conhecida de SUBSET-SUM, a redução e o certificado provam que PARTITION é NP-completa.

SUBGRAPH-ISOMORPHISM pergunta se um padrão $H$ ocorre como subgrafo de $G$. É NP-completa por redução a partir de CLIQUE, ou seja CLIQUE $\le_p$ SUBGRAPH-ISOMORPHISM: o padrão é o grafo completo $K_k$ e o grafo maior é a entrada de CLIQUE. Há clique de tamanho $k$ se e só se $K_k$ ocorre como subgrafo.

Em árvores, a cobertura ótima de vértices tem dois estados por vértice. Enraíza a árvore e define $C_1(u)$ como o mínimo da subárvore quando escolhemos $u$, e $C_0(u)$ quando o excluímos:

$$C_1(u)=1+\sum_{v\text{ filho de }u}\min(C_0(v),C_1(v)),\qquad C_0(u)=\sum_{v\text{ filho de }u}C_1(v).$$

Se $u$ não é escolhido, cada filho tem de cobrir a aresta que os liga. Se é escolhido, essa aresta já está coberta e cada filho pode usar o estado mais barato. Nas folhas, os valores são 1 e 0. Processar de baixo para cima visita cada aresta uma vez, dando $O(n)$ tempo e espaço; a resposta é o mínimo dos dois estados da raiz.

Outras restrições também podem tornar o problema tratável. Com apenas $k$ objetos excecionais e $k$ constante, enumerar os $2^k$ subconjuntos excecionais e completar cada resto com o método polinomial da parte regular dá tempo polinomial para cada $k$ fixo: no caso de pesos iguais, o resto escolhe os valores mais altos que cabem após ordenar, em $O(n\log n)$. Se o resto exigisse DP com tabela em $W$, o total seria apenas pseudopolinomial em $W$, não polinomial no tamanho binário. As hipóteses de $k$ fixo e de resto polinomial fazem parte do resultado.

Garantia de aproximação

Os algoritmos executados estão em aproximações com garantia. Aqui fica só o vocabulário. Para custos positivos e fator $\rho\ge1$, uma aproximação de minimização garante $C\le\rho C^*$. Para maximização garante $C\ge C^*/\rho$. Deve também produzir uma solução admissível e correr em tempo polinomial. Uma heurística sem prova pode funcionar bem, mas não tem automaticamente essa garantia.

Um esquema de aproximação permite escolher $\varepsilon>0$ e fator $1+\varepsilon$. Num PTAS, o tempo é polinomial no tamanho da entrada para cada $\varepsilon$ fixo; num FPTAS, é polinomial também em $1/\varepsilon$. A precisão pode aumentar o custo, e essa dependência faz parte do resultado.