Turmas - 1º Semestre de 2026(Marinha, 2011) O problema P versus NP é uma das maiores questões em aberto na ciência da computação. Em 2000, foi incluído entre os sete Problemas do Prêmio Millennium do Clay Mathematics Institute. Embora o consenso científico aponte que P ≠ NP, nenhuma demonstração formal foi estabelecida, mantendo a questão como um dos grandes desafios não resolvidos da matemática e da computação teórica. Em relação às classes de complexidade de problemas, assinale a opção correta.
A A classe de problemas em P consiste nos problemas que, dado um "certificado" de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.
B Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.
C A classe de problemas NP consiste nos problemas que não pertencem à classe P, e por isso são problemas não "verificáveis" em tempo polinomial.
D A busca binária é um problema NP-completo, dependendo do tamanho da entrada.
E Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.
A A classe de problemas em P consiste nos problemas que, dado um "certificado" de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.
Essa é a definição da classe NP, não de P. A classe P contém os problemas que podem ser resolvidos em tempo polinomial por uma Máquina de Turing determinística. A verificação de certificados em tempo polinomial é o que caracteriza NP.
B Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.
Esta é uma propriedade fundamental dos problemas NP-completos. Por definição, todo problema em NP pode ser reduzido a qualquer problema NP-completo em tempo polinomial. Portanto, se existir um algoritmo polinomial para um único problema NP-completo, podemos resolver qualquer problema de NP reduzindo-o a esse problema e aplicando o algoritmo polinomial. Isso implicaria que P = NP.
C A classe de problemas NP consiste nos problemas que não pertencem à classe P, e por isso são problemas não "verificáveis" em tempo polinomial.
A classe NP é definida exatamente como o conjunto de problemas cujas soluções podem ser verificadas em tempo polinomial. Além disso, P ⊆ NP, ou seja, todos os problemas de P também pertencem a NP. A afirmação contradiz a definição formal.
D A busca binária é um problema NP-completo, dependendo do tamanho da entrada.
A busca binária executa em O(log n), que é um tempo polinomial. Portanto, é um problema da classe P. Problemas NP-completos são os mais difíceis dentro de NP e não mudam de classe conforme o "tamanho da entrada"; a classificação é assintótica e teórica.
E Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.
Todo problema em P também está em NP. Se um algoritmo determinístico resolve o problema em tempo polinomial, ele certamente pode verificar um certificado em tempo polinomial (basta executar o algoritmo e comparar o resultado). A afirmação inverte a relação de subconjunto.
Ybadoo - Soluções em Software Livre • Copyright 2009/2026 • 