|
P-completoNa teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como:
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çãoA 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-completosO 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 2n. 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:
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.[1] Problemas que não se sabe se estão em P-completoNã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. Notas e referências
Biobliografia
|