NP é a classe de linguagens que possuem verificadores de tempo polinomial
A classe NP, que significa "tempo polinomial não determinístico", é um conceito fundamental na teoria da complexidade computacional, um subcampo da ciência da computação teórica. Para compreender o NP, é preciso primeiro compreender a noção de problemas de decisão, que são questões com resposta sim ou não. Uma linguagem neste contexto refere-se a um conjunto de cadeias de caracteres em algum alfabeto, onde cada cadeia de caracteres codifica uma instância de um problema de decisão.
Diz-se que uma linguagem (L) está em NP se existe um verificador de tempo polinomial para (L). Um verificador é um algoritmo determinístico (V) que recebe duas entradas: uma instância (x) e um certificado (y). O certificado (y) também é conhecido como “testemunha” ou “prova”. O verificador (V) verifica se o certificado (y) confirma que (x) pertence ao idioma (L). Formalmente, uma linguagem (L) está em NP se existe um algoritmo de tempo polinomial (V) e um polinômio (p(n)) tal que para cada string (x em L), existe uma string (y) com ( |y| leq p(|x|)) e (V(x, y) = 1). Por outro lado, para cada string (x notin L), não existe string (y) tal que (V(x, y) = 1).
Para elucidar este conceito, considere o conhecido problema da "satisfatibilidade booleana" (SAT). O problema SAT pergunta se existe uma atribuição de valores verdadeiros a variáveis em uma determinada fórmula booleana, de modo que a fórmula seja avaliada como verdadeira. O problema SAT está em NP porque, dada uma fórmula booleana (phi) e uma atribuição (alfa) de valores verdade às suas variáveis, pode-se verificar em tempo polinomial se (alfa) satisfaz (phi). Aqui, a instância ( x ) é a fórmula booleana ( phi ) e o certificado ( y ) é a atribuição ( alpha ). O verificador (V) verifica se (alfa) torna (phi) verdadeiro, o que pode ser feito em tempo polinomial em relação ao tamanho de (phi).
Outro exemplo ilustrativo é o problema do “Caminho Hamiltoniano”. Este problema pergunta se existe um caminho em um determinado grafo que visita cada vértice exatamente uma vez. O problema do Caminho Hamiltoniano também está em NP porque, dado um grafo ( G ) e uma sequência de vértices ( P ), pode-se verificar em tempo polinomial se ( P ) é um caminho hamiltoniano em ( G ). Neste caso, a instância (x) é o grafo (G), e o certificado (y) é a sequência de vértices (P). O verificador (V) verifica se (P) forma um caminho hamiltoniano, o que pode ser feito em tempo polinomial em relação ao tamanho de (G).
O conceito de verificabilidade em tempo polinomial é importante porque fornece uma maneira de caracterizar problemas que são verificáveis eficientemente, mesmo que encontrar a solução possa ser computacionalmente inviável. Isso leva à famosa questão de se ( P = NP ), que pergunta se todo problema cuja solução pode ser verificada em tempo polinomial também pode ser resolvido em tempo polinomial. A classe ( P ) consiste em problemas de decisão que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística. Se ( P = NP ), isso significaria que todo problema com um verificador de tempo polinomial também tem um solucionador de tempo polinomial. Essa questão continua sendo um dos problemas em aberto mais importantes na ciência da computação.
Uma das principais propriedades do NP é que ele é fechado sob reduções em tempo polinomial. Uma redução em tempo polinomial de uma linguagem ( L_1 ) para uma linguagem ( L_2 ) é uma função computável em tempo polinomial ( f ) tal que ( x in L_1 ) se e somente se ( f(x) in L_2 ). Se existe uma redução em tempo polinomial de (L_1) para (L_2) e (L_2) está em NP, então (L_1) também está em NP. Esta propriedade é fundamental no estudo da completude do NP, que identifica os problemas “mais difíceis” no NP. Um problema é NP-completo se estiver em NP e todo problema em NP puder ser reduzido a ele em tempo polinomial. O problema SAT foi o primeiro problema comprovado como NP-completo e serve de base para provar a NP-completude de outros problemas.
Para ilustrar melhor o conceito de verificabilidade em tempo polinomial, considere o problema da "Soma do Subconjunto". Este problema pergunta se existe um subconjunto de um determinado conjunto de inteiros que soma um valor alvo especificado. O problema da soma do subconjunto está em NP porque, dado um conjunto de inteiros ( S ), um valor alvo ( t ) e um subconjunto ( S' ) de ( S ), pode-se verificar em tempo polinomial se a soma dos elementos em (S') é igual a (t). Aqui, a instância ( x ) é o par ( (S, t) ) e o certificado ( y ) é o subconjunto ( S' ). O verificador ( V ) verifica se a soma dos elementos em ( S' ) é igual a ( t ), o que pode ser feito em tempo polinomial em relação ao tamanho de ( S ).
A importância da verificabilidade em tempo polinomial se estende além das considerações teóricas. Em termos práticos, significa que para problemas em NP, se uma solução proposta (certificado) for fornecida, ela pode ser verificada de forma eficiente. Isso tem implicações significativas para protocolos criptográficos, problemas de otimização e vários campos onde verificar a correção de uma solução é importante.
Resumindo, a classe NP abrange problemas de decisão para os quais uma solução proposta pode ser verificada em tempo polinomial por um algoritmo determinístico. Este conceito é fundamental na teoria da complexidade computacional e tem implicações profundas tanto para os aspectos teóricos quanto práticos da ciência da computação. O estudo de NP, verificabilidade em tempo polinomial e conceitos relacionados, como completude de NP, continua a ser uma área de pesquisa vibrante e crítica.
Outras perguntas e respostas recentes sobre Complexidade:
- A classe PSPACE não é igual à classe EXPSPACE?
- A classe de complexidade P é um subconjunto da classe PSPACE?
- Podemos provar que as classes Np e P são iguais encontrando uma solução polinomial eficiente para qualquer problema NP completo em uma TM determinística?
- A classe NP pode ser igual à classe EXPTIME?
- Existem problemas no PSPACE para os quais não existe um algoritmo NP conhecido?
- Um problema SAT pode ser um problema NP completo?
- Um problema pode estar na classe de complexidade NP se houver uma máquina de turing não determinística que irá resolvê-lo em tempo polinomial
- P e NP são realmente da mesma classe de complexidade?
- Toda linguagem livre de contexto na classe de complexidade P?
- Existe uma contradição entre a definição de NP como uma classe de problemas de decisão com verificadores de tempo polinomial e o fato de que problemas da classe P também possuem verificadores de tempo polinomial?
Veja mais perguntas e respostas em Complexidade