NP (complexidade)

O NP classe é um muito importante classe da teoria da complexidade . A abreviatura NP significa “ tempo polinomial não determinístico ”. Um problema de decisão está em NP se for decidido por uma máquina de Turing não determinística em tempo polinomial em relação ao tamanho da entrada. Intuitivamente, isso equivale a dizer que podemos verificar “rapidamente” ( complexidade polinomial ) se uma solução candidata é de fato uma solução. Por exemplo, considere o problema de decisão do caixeiro viajante que, dado um inteiro k e um conjunto de cidades separadas por distâncias, determina se existe um circuito de comprimento menor que k que passa uma e apenas uma vez por todas as cidades. Verificamos “rapidamente” se uma solução candidata, aqui qualquer caminho, é de fato uma solução, ou seja, é realmente um circuito de comprimento menor que k e que de fato passa uma e apenas uma vez por todas as cidades.

Um dos grandes problemas em aberto da ciência da computação teórica é o Problema P ≟ NP .

Definições

Definição por máquina não determinística

Chamamos NTIME ( t ( n )) a classe de problemas de decisão que podem ser resolvidos no tempo da ordem de magnitude de t ( n ) em uma máquina de Turing não determinística (onde n é o tamanho da entrada).

Então NP = NTIME ( ). $\ scriptstyle \ cup _ {{c> 1}}$ $\ scriptstyle n ^ {c}$

Definição por certificado

Em um alfabeto , uma linguagem está em NP se existe uma máquina de Turing polinomial e uma determinística em tempo polinomial , como para uma palavra de tamanho : (onde significa que a máquina aceita na entrada ( x , u )). $\ Sigma$ $eu$ $P$ $M$ $x$ $não$ $x \ em L \ Leftrightarrow \ existe u \ in \ Sigma ^ {{P (n)}}, M (x, u) = 1$ $M (x, u) = 1$

Em outras palavras, existe uma "pista", chamada de certificado , que pode rapidamente provar que a palavra está no idioma.

NP-completude

Os problemas NP-completos são NP-difíceis também são NP-difíceis. Esses são os problemas mais difíceis da classe no sentido de que qualquer problema de NP pode ser reduzido a esses problemas por certas reduções , em particular reduções polinomiais .

Muitos problemas foram identificados como NP-completos, incluindo o problema SAT ou o Circuito Hamiltoniano

Relações com outras classes

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

Nas aulas habituais, também podemos citar um upgrade: NP PSPACE . $\ subseteq$

NP também permite definir co-NP , a classe complementar. Essas duas classes formam o primeiro nível da hierarquia polinomial . O teorema de Karp-Lipton afirma que se NP admite circuitos de tamanhos polinomiais, então a hierarquia polinomial entra em colapso para o nível 2.

Outras caracterizações

Um dos grandes resultados da complexidade descritiva é o teorema de Fagin , que mostra a equivalência entre os problemas do NP e aqueles expressáveis na lógica do ESO.
O teorema PCP permite descrever a classe NP no contexto de um sistema de prova interativo , mais precisamente PCP [O (log n ), O (1)] = NP .

Bibliografia

(pt) Sanjeev Arora e Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 )

Link externo

(fr) A classe NP no Zoológico de Complexidade

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 2.1, “ A classe NP ”.
Consulte a Lista de problemas NP-completos .