P-completo

Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como:

1. que problemas são difíceis de paralelizar eficientemente, e;
2. que problemas são difíceis de resolver com espaço limitado.

Formalmente, um problema de decisão é P-completo (completo para a classe P de complexidade) se ele está em P e se qualquer problema em P é redutível a ele usando uma função de redução adequada.

O tipo específico de redução usado varia e pode afetar o conjunto exato de problemas. Se usarmos reduções NC, isto é, reduções que podem operar em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores, então todos os problemas P-completos estão fora da classe NC e, portanto, não podem ser paralelizados eficientemente, sob a suposição não comprovada de que NC ≠ P. Se nós usarmos a redução log-space mais fraca, isto continua verdadeiro, mas adicionalmente vemos que todos os problemas P-completos estão fora da classe L (também conhecida como classe LSPACE) sob a suposição mais fraca não comprovada de que L ≠ P. Neste último caso, o conjunto P-completo pode ser menor.

Motivação

A classe P, normalmente considerada como o conjunto de todos os problemas "tratáveis" por um computador sequencial, contém a classe NC, que consiste naqueles problemas que podem ser resolvidos eficientemente por um computador paralelo. Isto acontece porque computadores paralelos podem ser simulados em máquinas sequenciais.

Não se sabe se NC = P. Em outras palavras, ainda não sabemos se existem problemas tratáveis que são inerentemente sequenciais. Assim como suspeita-se que P não é igual a NP, também suspeita-se que NC não é igual a P.

Da mesma forma, a classe L contém todos os problemas que podem ser resolvidos por um computador sequencial usando espaço logarítmico. Tais máquinas rodam em tempo polinomial porque elas podem ter um número polinomial de configurações. Suspeita-se que L ≠ P; isto é, que alguns problemas que podem ser resolvidos em tempo polinomial também requerem mais do que espaço logarítmico.

De modo similar ao uso dos problemas NP-completos para analisar a questão P = NP, os problemas P-completos, vistos como os problemas "provavelmente não paralelizáveis" ou "provavelmente inerentemente sequenciais", também são úteis de maneira semelhante ao estudo da questão NC = P. Encontrar uma forma eficiente de paralelizar a solução de algum problema P-completo é equivalente a provar que NC = P. Isto também pode ser pensado como "problemas que requerem espaço super-logarítmico"; uma solução em espaço logarítmico para um problema P-completo (usando a definição baseada nas reduções em espaço logarítmico) implicaria em L = P.

A lógica por trás disso é análoga a lógica de que uma solução em tempo polinomial para um problema NP-completo provaria que P = NP: se nós temos uma redução NC a partir de algum problema em P para um problema A, e uma solução NC para A, então NC = P. Da mesma forma, se nós temos uma redução em espaço logarítmico a partir de algum problema em P para um problema A, e uma solução em espaço logarítmico para A, então L = P.

Problemas P-completos

O problema P-completo mais básico é: dado uma máquina de Turing, uma entrada para esta máquina e um número T (escrito no sistema unário), esta máquina para ao executar a entrada nos primeiros T passos? É claro que este problema é P-completo: se nós podemos paralelizar uma simulação geral de um computador sequencial, então nós seremos capazes de paralelizar qualquer programa que seja executado naquele computador. Se este problema estiver em NC, então todos os outros problemas em P estarão. Se o número de passos for escrito em binário, o problema é EXPTIME-completo.

Este problema ilustra um truque comum na teoria da P-completude. Não estamos realmente interessados em saber se um problema pode ser resolvido rapidamente em uma máquina paralela. Estamos apenas interessados em saber se uma máquina paralela pode resolvê-los "muito mais" rapidamente do que uma máquina sequencial. Portanto, nós temos que reformular o problema de modo que a versão sequencial esteja em P. É por isso que este problema exigiu que T fosse escrito em unário. Se um número T for escrito como um número binário (uma cadeia de n 1's e 0's, onde n = log T), então o algoritmo sequencial óbvio pode tomar um tempo 2ⁿ. Por outro lado, se T for escrito como um número unário (uma cadeia de n 1's, onde n = T), então o algoritmo gastará apenas um tempo n. Ao escrever T em unário ao invés de binário, nós teremos reduzido o algoritmo sequencial óbvio de um tempo exponencial para um tempo linear. Isto coloca o problema sequencial em P. Logo, ele estará em NC se e somente se ele for paralelizável.

Muitos outros problemas foram provados estar na classe P-completo, e portanto, acredita-se fortemente que eles sejam inerentemente sequenciais. Entre eles estão os seguintes problemas, tanto na forma apresentada, quanto na forma de problema de decisão:

• Problema do Valor do Circuito (VALOR-CIRCUITO) - Dado um circuito booleano, as entradas do circuito e uma porta lógica no circuito, calcula a saída da porta
• Programação linear - Maximizar uma função objetivo linear para uma desigualdade linear de restrições
• Ordenação Lexicográfica por Busca em Profundidade - Dado um grafo com listas de adjacência ordenadas fixas e nós u e v, o vértice u é visitado antes do vértice v numa busca em profundidade induzida pela ordem das listas de adjacência?
• Problema da Aceitação de Gramáticas Livres-do-Contexto: Dada uma gramática livre de contexto e uma cadeia w, w pode ser gerada por esta gramática?
• Problema da satisfazibilidade de Horn (HORNSAT): dado um conjunto de cláusulas de Horn, existe alguma valoração que as satisfaçam? Esta é a versão P para o problema da satisfazibilidade booleana.
• Jogo da Vida: Dado uma configuração inicial do Jogo da Vida de Conway, uma célula particular, e um tempo T (em unário), esta célula estará viva após T passos?
• Algoritmo de Compressão de Dados LZW (paradigma 1978) - dadas cadeias s e t, a compressão de s com um método LZ78 irá adicionar t ao dicionário? (note que para a compressão LZ77 como o gzip, é consideravelmente mais fácil já que o problema se reduz a pergunta "t está em s?".)
• Inferência de tipo para tipos parciais - Dado um termo sem tipo do cálculo lambda, determinar se este termo possui um tipo parcial.

Para provar que um dado problema é P-completo, normalmente tenta-se reduzir um problema P-completo conhecido para o problema em questão.

Em 1999, Jin-Yi Cai e D. Sivakumar, com base nos trabalhos de Ogihara, mostraram que se existe uma linguagem esparsa que é P-completa, então L = P.

Problemas que não se sabe se estão em P-completo

Não se sabe se alguns problemas estão em NP-difícil, nem em P. Esses problemas (por exemplo, fatoração de inteiros) são suspeitos de serem difíceis. De modo similar, existem problemas que não se sabe se estão em P-completo ou NC, mas acredita-se que são difíceis de paralelizar. Exemplos incluem formas do problema de decisão para encontrar o máximo divisor comum de dois números e determinar qual resposta o algoritmo de Euclides estendido retornaria ao receber dois números.

Biobliografia

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4. — Develops the theory, then catalogs 96 P-Complete problems.
• Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of P-Complete Problems. Kyushu University, RIFIS-TR-CS-17. December 1990.