P (complexidade)

A classe P , às vezes também conhecida como PTIME ou DTIME (n O (1) ), é uma classe muito importante da teoria da complexidade , um campo da ciência da computação teórica e da matemática . Por definição, um problema de decisão está em P se for decidido por uma máquina de Turing determinística em tempo polinomial em relação ao tamanho da entrada. Dizemos que o problema é resolvido em tempo polinomial .

Os problemas em P são considerados "factíveis" ( factíveis em inglês), fáceis de resolver (no sentido de que pode ser feito de forma relativamente rápida). Esta é a tese de Cobham emitida pelo cientista americano Alan Cobham. René Lalement atribui essa tese a Cook. A classe P está incluída na classe NP , levando a um dos grandes problemas em aberto da teoria da complexidade, a saber: P é igual a NP?

Exemplos de problemas em P

Um problema está em P se houver um algoritmo que o decida em tempo polinomial. Deixe-nos citar:

2SAT as restrições e HORNSAT SAT problema está em P .
Conectividade em um gráfico: Um exemplo de problema polinomial é o de conectividade em um gráfico. Dado um gráfico com n vértices (consideramos que o tamanho dos dados, portanto do gráfico, é o seu número de vértices), trata-se de saber se todos os pares de vértices estão ligados por um caminho. Um algoritmo de passagem em profundidade constrói uma árvore que abrange o gráfico a partir de um vértice. Se esta árvore contém todos os vértices do gráfico, o gráfico está conectado. O tempo necessário para construir esta árvore é no máximo c . n ² (onde C é uma constante e n o número de vértices do gráfico), de modo que o problema é na classe P .

Além disso, às vezes a prova de associação em P , que geralmente é feita pela descoberta de um algoritmo polinomial, levou anos de pesquisa:

O teste de primalidade AKS é um algoritmo que mostra que o problema de se um inteiro é primo ou não pode ser resolvido por um algoritmo polinomial.

Programação linear: O ponto interior algoritmos utilizados para classificar a programação linear na classe P . Este problema é mesmo P -completo .

Definições formais

Definição clássica usando máquinas de Turing

Denotamos por TEMPO ( t ( n )) a classe de problemas de decisão que podem ser decididos no tempo da ordem de magnitude de t ( n ) em uma máquina determinística (onde n é o tamanho da entrada). Então, por definição

{\ mathrm {P}} = \ bigcup _ {{c> 1}} {\ mathrm {TEMPO}} (n ^ {c}).

Definição com circuitos

P também pode ser definido usando famílias uniformes de circuitos booleanos . Uma linguagem L está em P se, e somente se, existe uma família de circuitos booleanos , uniforme em tempo polinomial (ou seja, há uma máquina de Turing determinística que produz na entrada 1 n ), como ${\ displaystyle \ {C_ {n}: n \ in \ mathbb {N} \}}$ $C_ {n}$

para tudo , pegue n bits de entrada e retorne um bit de saída $n \ in \ mathbb {N}$ $C_ {n}$
Para todo x em L , ${\ displaystyle C_ {| x |} (x) = 1}$
Para todo x que não está em L , ${\ displaystyle C_ {| x |} (x) = 0}$

A definição por circuitos pode ser enfraquecida usando uma família uniforme no espaço logarítmico e sempre dá uma definição equivalente para a classe P. Se relaxarmos a suposição de uniformidade, definiremos a classe P / poli .

Relações com outras classes

Temos a inclusão óbvia P NP , mas uma das grandes questões em aberto na ciência da computação teórica é o problema P = NP? . $\ scriptstyle \ subseteq$

Podemos colocar P na hierarquia das línguas, classificadas de acordo com o espaço requerido: ele contém NL (a classe de problemas que podem ser resolvidos em uma máquina não determinística no espaço logarítmico) e está contido por PSPACE (a classe de problemas que pode ser resolvido em uma máquina não determinística no espaço logarítmico). resolvido no espaço polinomial). As inclusões são as seguintes (não sabemos se são restritas):

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE P ≠ EXPTIME (de acordo com o teorema da hierarquia determinística do tempo )

Além disso, P é o primeiro nível da hierarquia polinomial . E P está incluído nas classes polinomiais em máquinas mais poderosas (quântica ou usando o acaso, por exemplo), como ZPP , BPP e BQP .

Problemas de P-completo

Um problema de decisão A é dito ser P - completo , ou completo para a classe P , se for da classe P e se qualquer problema da classe P pode ser reduzido a A no espaço logarítmico (ou seja, que a tradução de uma instância x do problema para uma instância de A pode ser feito usando um espaço O (log | x |)). Os problemas a seguir são P- completos .

Corno-SAT: o problema sab geralmente é NP-completo , mas a sua restrição define cláusulas de Horn é em P . É P-completo.
Problema de avaliação de um circuito : este problema, em inglês circuit value problem (CVP), consiste em determinar se, para um dado circuito booleano , o resultado da função realizada em uma dada entrada corresponde a um dado valor.
O problema de saber se a linguagem denotada por uma gramática algébrica está vazia ou não.
Decida se a linguagem de uma gramática algébrica é infinita.
O problema de verificação de modelo ( verificação de modelo em inglês), uma forma de lógica temporal CTL, está em P e foi comprovada como P-completa. Mais precisamente, a prova mostra que a verificação do modelo de uma fórmula do fragmento sintático de CTL com os operadores AX (para qualquer sucessor) e EX (há um sucessor) é P-difícil. Assim, a verificação do modelo de uma fórmula da lógica modal K é P-completa.
O problema do fluxo máximo e, portanto, da programação linear real .

Se houver uma linguagem vazia que seja P-completa, então P = LOGSPACE .

Propriedades adicionais

Em alguns casos, falamos de algoritmos de tempo polinomial forte ou fraco . Essa distinção existe para problemas cuja entrada contém inteiros. Falamos de tempo polinomial fraco se os inteiros devem ser dados em escrita unária (ou seja, o número n conta como um tamanho n ) para ter um tempo polinomial, e falamos de tempo polinomial fortemente se mesmo a escrita compacta ( n tem log de tamanho ( n )) fornece complexidade polinomial.

Veja também

Classe NP

P / poli

Bibliografia

(pt) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 1 ("O modelo computacional - e por que isso não importa")

Link externo

(pt) A classe P no Complexity Zoo

Notas e referências

(em) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 1 nas notas históricas.
Alan Cobham, " A dificuldade computacional intrínseca das funções ", Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science , North Holland,1965.
René Lalement, resolução de redução lógica , Masson, p. 344
Richard E. Ladner , “ O problema do valor do circuito é o espaço de log completo para P, ” ACM SIGACT News , vol. 7, n o 1,1 r janeiro 1975, p. 18–20 ( ISSN 0163-5700 , DOI 10.1145 / 990518.990519 , lido online , acessado em 30 de outubro de 2018 )
" Computational Complexity: A Modern Approach / Sanjeev Arora e Boaz Barak " , em theory.cs.princeton.edu (acessado em 30 de outubro de 2018 ) , p. 119, Th. 6,30
Neil D. Jones e William T. Laaser , " Complete Problems for Deterministic Polynomial Time, " Theor. Comput. Sci. , vol. 3, n o 1,1976, p. 105-117.
" math.stackexchange.com "
André Arnold e Paul Crubille , “ Um Algoritmo Linear para Resolver Equações de Ponto Fixo em Sistemas de Transição ”, Inf. Processar. Lett. , vol. 29, n o 2Setembro de 1988, p. 57-66 ( ISSN 0020-0190 , DOI 10.1016 / 0020-0190 (88) 90029-4 , lido online , acessado em 27 de fevereiro de 2019 )
EM Clarke , EA Emerson e AP Sistla , “ Verificação automática de sistemas concorrentes de estado finito usando especificações lógicas temporais ”, ACM Trans. Programa. Lang. Syst. , vol. 8, n o 2Abril de 1986, p. 244-263 ( ISSN 0164-0925 , DOI 10.1145 / 5397.5399 , ler online , acessado em 27 de fevereiro de 2019 )
Philippe Schnoebelen , A Complexidade do Temporal Logic Modelo Verificação ,1 ° de janeiro de 2002( leia online ).
(em) " O problema de fluxo máximo é o espaço de registro para P completo " , Theoretical Computer Science , vol. 21, n o 1,1 r out 1982, p. 105-111 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (82) 90092-5 , ler online , acessado em 8 de novembro de 2018 )
Jin-Yi Cai e D. Sivakumar , “ Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis, ” Journal of Computer and System Sciences , vol. 58, n o 21 r abr 1999, p. 280–296 ( ISSN 0022-0000 , DOI 10.1006 / jcss.1998.1615 , ler online , acessado em 14 de julho de 2019 )