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: que problemas são difíceis de paralelizar eficientemente, e; 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.