Complexidade

A máquina de Turing que marca pares em $a^nb^n$ termina, mas regressa várias vezes sobre a entrada. A complexidade mede quantos passos essas varreduras exigem quando a entrada cresce.

Esta página é uma extensão ao percurso de linguagens formais. Usa a distinção entre reconhecedor e decisor; a profundidade da avaliação atual não está confirmada. Uma cota $O(f(n))$ limita o custo por um múltiplo fixo de $f(n)$ para entradas suficientemente grandes.

Medir o tamanho da entrada

O tamanho $n$ é o comprimento da codificação, não necessariamente o valor numérico descrito. Um inteiro positivo $N$ em binário usa $\lfloor\log_2N\rfloor+1$ bits. Um algoritmo que faz $N$ passos pode ser exponencial nesse número de bits.

Por exemplo, representar $1024$ em binário precisa de 11 bits. Experimentar todos os inteiros de $1$ a $N$ não passa a ser polinomial no comprimento da entrada só porque faz $O(N)$ passos.

Para um decisor, o tempo no pior caso $T(n)$ é o maior número de passos entre as entradas de comprimento $n$. Numa comparação assintótica, $O(n^k)$, para $k$ fixo, é tempo polinomial. $2^n$ e $n!$ não são polinomiais.

A classe polinomial mantém-se nas simulações usuais entre modelos razoáveis de computação. Isso não diz que todo o algoritmo polinomial é rápido na prática: $n^{100}$ ou uma constante enorme podem torná-lo inutilizável.

O custo depende da representação

Converter uma descrição antes de decidir uma pergunta pode tornar o problema maior. Se a palavra tem comprimento $n$, o autómato tem $s$ estados e o alfabeto é fixo:

Tarefa	Custo ou tamanho relevante
Simular um DFA	$O(n)$ passos com acesso direto à tabela.
Simular um NFA	$O(ns^2)$ numa implementação por conjuntos e tabela de destinos.
Determinizar um NFA	Até $2^s$ estados; a construção pode produzir uma descrição exponencial.
Thompson para uma expressão de comprimento $r$	$O(r)$ estados e arestas.
CYK para uma CFG fixa em CNF	$O(n^3)$ tempo e $O(n^2)$ espaço.

Para testar uma só palavra num NFA, não precisas de materializar o DFA inteiro. Segue o conjunto de estados possíveis e evita o crescimento exponencial da conversão. São custos de tarefas diferentes, não uma contradição.

Na eliminação de estados, há um número polinomial de atualizações de rótulos, mas cada rótulo é uma expressão que pode crescer muito. Contar atualizações sem contar o tamanho das expressões não prova tempo polinomial para escrever o resultado.

P: decidir em tempo polinomial

P é a classe das linguagens decidíveis por TM determinística em tempo polinomial. A pertença a uma linguagem regular está em P: um DFA fixo lê a entrada em $O(n)$. Para uma CFG fixa, CYK decide em $O(n^3)$.

Classes como P e NP definem-se para problemas de decisão, com resposta sim ou não. Um problema de otimização pode ter uma versão de decisão, por exemplo: em vez de pedir o menor percurso, perguntar se existe um percurso de custo no máximo $k$.

NP: certificados verificáveis

NP contém as linguagens para as quais uma resposta sim pode ter um certificado de comprimento polinomial, verificável em tempo polinomial. Formalmente, existe um verificador $V$ e um polinómio $p$ tais que:

$$w\in L\iff\exists c,\quad |c|\le p(|w|) \ \text{e}\ V(w,c)\text{ aceita}.$$

O verificador tem de terminar em tempo polinomial e rejeitar certificados inválidos. Para uma entrada fora da linguagem, nenhum certificado pode fazê-lo aceitar.

Num grafo não dirigido com vértices $\{1,2,3,4\}$ e arestas $\{\{1,2\},\{2,3\},\{3,4\}\}$, a lista $(1,2,3,4)$ certifica um caminho hamiltoniano: visita todos os vértices uma vez e usa apenas arestas existentes. $(1,3,2,4)$ falha já no primeiro par, porque não existe aresta entre 1 e 3.

Não precisas de descobrir a lista para provar pertença a NP, mas não basta dizer que uma resposta sim tem alguma prova: é preciso limitar o comprimento do certificado e o tempo de verificação.

Verificador concreto com tamanho e custo

No problema do caminho hamiltoniano, a entrada $w$ codifica um grafo com $n$ vértices e $m$ arestas. O certificado $c$ é uma lista de $n$ vértices. Verifica a lista em $O(n^2)$ comparações de identificadores, cada par consecutivo numa matriz de adjacência, e rejeita se algum teste falhar.

Com vértices numerados, o comprimento $|c|$ é $O(n\log(n+1))$ bits. Assume uma codificação explícita do grafo que enumera todos os vértices, incluindo os isolados; assim este tamanho é polinomial em $|w|$. As comparações de identificadores custam ainda $O(\log(n+1))$ operações de bits cada uma, e o verificador corre em tempo polinomial, rejeitando certificados inválidos.

Para $w$ fora da linguagem, nenhum $c$ passa nos dois testes. Encontrar a lista pode ser difícil; verificá-la é barato. É essa assimetria que NP formaliza.

Equivalentemente, NP é o conjunto de linguagens decididas por TM não determinística em tempo polinomial: um ramo escolhe o certificado e verifica-o. O limite temporal aplica-se a todos os ramos. NP significa tempo polinomial não determinístico, não “não polinomial”.

Relação entre P e NP

Temos $P\subseteq NP$, pois um verificador pode ignorar o certificado e correr o decisor polinomial. Continua por resolver se $P=NP$.

NP contém problemas fáceis, incluindo todos os de P. Dizer que um problema está em NP não prova que não tenha algoritmo polinomial. Dizer que o melhor algoritmo que conheces é exponencial também não prova esse limite inferior.

Reduções polinomiais

Escreve $A\le_p B$ se existe uma função $f$, computável em tempo polinomial, com

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

A transformação tem de preservar respostas sim e não e produzir uma entrada de tamanho polinomial. Se $B\in P$, então $A\in P$: calcula $f(x)$ e usa o decisor de $B$.

Exemplo: satisfazer com pelo menos um verdadeiro

SAT pergunta se uma fórmula booleana tem uma atribuição que a torna verdadeira. Considera a variante que exige também que pelo menos uma variável tenha valor verdadeiro. Para transformar uma fórmula $\varphi$ de SAT, cria uma variável nova $z$ e usa $f(\varphi)=\varphi\land z$.

Se $\varphi$ é satisfazível, prolonga a atribuição com $z$ verdadeiro. Se $\varphi\land z$ é satisfazível, a restrição da atribuição às variáveis antigas satisfaz $\varphi$. A variável nova garante a condição adicional. O tamanho aumenta apenas por uma conjunção e uma variável, logo a transformação é polinomial.

As duas implicações são a prova da redução. Exemplos isolados não substituem essa correspondência.

NP-difícil e NP-completo

Um problema $B$ é NP-difícil se todo o problema de NP se reduz a $B$ em tempo polinomial. É NP-completo se, além disso, $B\in NP$.

Para provar NP-completude, descreve primeiro certificado, tamanho e verificador. Depois reduz a $B$ um problema já NP-completo, provando a equivalência e o custo. A transitividade das reduções transporta a dificuldade dos restantes problemas de NP.

SAT é NP-completo pelo teorema de Cook-Levin. Uma atribuição booleana é o seu certificado, mas isso só demonstra a parte $SAT\in NP$; a dificuldade exige o outro argumento do teorema.

Se algum problema NP-completo estiver em P, então $P=NP$. Se um problema for apenas NP-difícil, não podes concluir que pertença a NP, nem que seja decidível. A dificuldade e a pertença são afirmações distintas.