P (complexidade)

Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística. Qualquer problema deste conjunto pode ser resolvido por um algoritmo com tempo de execução O(n^{k}), (com k constante).

Podemos ter a classe P como a classe de problemas que são solúveis para um computador real. Embora esta definição não seja exata, é uma boa aproximação para servir de base para nosso estudo.

Definição

Uma linguagem L está em P se e somente se existe uma máquina de Turing determinística M que:

M roda em tempo polinomial para todas as entradas
Para cada x em L, M gera 1
Para cada x que não está em L, M gera 0

Problemas Notáveis em P

P é conhecido por conter vários problemas naturais, incluindo as versões de decisão de Programação linear, o cálculo do Máximo divisor comum e encontrar um emparelhamento máximo. Em 2002, foi mostrado que o problema em se determinar se um número é primo está em P.^[1]

Relação com as outras classes

A generalização de P é NP que é a classe de linguagens decidíveis em tempo polinomial em uma máquina de Turing não-determinística. Trivialmente, P é um subconjunto de NP. Embora ainda não seja provado, muitos especialistas acreditam que P é um subconjunto próprio de NP.^[2]

P também é conhecido por ser tão grande quanto L, a classe de problemas decidíveis em um espaço de memória logarítmico. Um decisor que usa espaço $O(\log n)$ não pode levar mais tempo do que $2^{O(\log n)}=n^{O(1)}$ porque isto é o número total de configurações possíveis, assim L é subconjunto de P. Porém, outro problema importante é saber se L = P. Sabemos que P = NL, que é a classe dos problemas solúveis em espaço logarítmico em uma maquina de Turing não-determinística, e que P não é maior do que PSPACE, a classe dos problemas decidíveis em espaço polinomial. Assim, não sabemos se P = PSPACE. Resumindo:

{\mbox{L}}\subseteq {\mbox{NL}}={\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}.

Aqui, EXPTIME é a classe dos problemas solúveis em tempo exponencial. De todas as classes mostradas acima, apenas duas restrições são conhecidas:

P está estritamente contido em EXPTIME. Consequentemente, todos os problemas EXPTIME-difíceis ficam fora de P e, pelo menos, uma contenção à direita de P é correta (na verdade, muitos acreditam que todas as três são corretas).
L está estritamente contido em PSPACE.

Os problemas mais difíceis de P são os problemas P-completos

Propriedades

Algoritmos em tempo polinomial são fechados sob composição. Intuitivamente, se alguém escreve uma função de tempo polinomial assumindo que as chamadas de função são em tempo constante e se as funções chamadas requerem tempo polinomial, então o algoritmo inteiro leva tempo polinomial. Isto é uma das razões principais de P ser considerada uma classe independente de máquina; qualquer recurso da máquina, como Acesso aleatório, que pode ser simulada em tempo polinomial, pode simplesmente ser composto com o algoritmo de tempo polinomial principal para reduzí-la em um algoritmo de tempo polinomial que pode ser rodada em uma máquina mais básica.

História

Dexter Kozen diz que pppp0Cobhpam e Jack Edmonds são geralmente creditados pela invenção da noção do tempo polinomial. Cobham inventou a classe como uma maneira robusta de caracterizar algoritmos eficientes, criando a tese de Cobham. No entanto, H.C. Pocklington, em um artigo de 1910,^[3]^[4] analisou dois algoritmos para resolver de congruências quadráticas, obervou que um teve tempo "proporcional a uma potência do logaritmo do módulo" e contrastou isso com uma que levou tempo proporcional ao "módulo ou sua raiz quadrada". Assim ele explicitou a diferença entre um algoritmo que roda em tempo polinomial contra um que não roda em tempo polinomial.

Referências

↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
↑ Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education, page 458, ISBN 0-02-360692-4
↑ Pocklington, H. C. (1910–1912). «The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity». Proc. Cambridge Phil. Soc. 16: 1–5
↑ Gautschi, Walter (1994). Mathematics of computation, 1943-1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia. Providence, RI: American Mathematical Society. pp. 503–504. ISBN 0-8218-0291-7

[1] Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

[2] Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education, page 458, ISBN 0-02-360692-4

[3] Pocklington, H. C. (1910–1912). «The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity». Proc. Cambridge Phil. Soc. 16: 1–5

[4] Gautschi, Walter (1994). Mathematics of computation, 1943-1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia. Providence, RI: American Mathematical Society. pp. 503–504. ISBN 0-8218-0291-7

[1]

[2]

[3]

[4]