O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação.

ENADE 2011 - QUESTÃO 36
O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação. Em linhas gerais, deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, também pode ser eficientemente obtida por um computador. Por “eficientemente” ou “eficiente” significa “em tempo polinomial”.

A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas entradas.

Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é chamada de classe NP.

Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos problemas.

Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações que se seguem. 

I. Existem problemas na classe P que não estão na classe NP.

II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.

III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.

IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.

É correto apenas o que se afirma em

A) I.

B) IV.

C) I e III.

D) II e III.

E) II e IV.

QUESTÃO ANTERIOR:

GABARITO:
D) II e III.

RESOLUÇÃO:
Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

PRÓXIMA QUESTÃO:

QUESTÃO DISPONÍVEL EM:

COMENTÁRIOS

Nome

curiosidades,2,enade,23,exercícios,4,inglês,1,português,1,provas,80,questão da albert einstein,21,questão da avança sp,40,questão da cespe,1,questão da famema,80,questão da famerp,52,questão da fatec,54,questão da fepese,80,questão da fgv,87,questão da fmabc,40,questão da fuvest,367,questão da oab,79,questão da santa casa,80,questão da uece,100,questão da uema,94,questão da ufrgs,325,questão da unesp,204,questão da unicamp,83,questão da uniceub,108,questão da unichristus,54,questão da unifenas,48,questão da unifesp,428,questão da unifor,64,questão da unioeste,80,questão da unitins,49,questão de administração,11,questão de administração pública,3,questão de agroindústria,1,questão de agronomia,20,questão de alemão,25,questão de atualidades,15,questão de biblioteconomia,15,questão de biologia,202,questão de biomedicina,14,questão de ciências,42,questão de ciências contábeis,7,questão de ciências econômicas,3,questão de ciências sociais,69,questão de concurso,561,questão de design,45,questão de direito,265,questão de direito penal,22,questão de direito processual penal,21,questão de direito tributário,5,questão de educação física,97,questão de enfermagem,5,questão de espanhol,85,questão de estatística,24,questão de filosofia,64,questão de física,215,questão de francês,33,questão de gastronomia,22,questão de geografia,326,questão de gestão ambiental,17,questão de gestão comercial,1,questão de gestão de recursos humanos,13,questão de história,246,questão de informática básica,10,questão de inglês,218,questão de italiano,25,questão de legislação,10,questão de literatura,48,questão de marketing,17,questão de matemática,382,questão de medicina,105,questão de música,84,questão de português,376,questão de processos gerenciais,23,questão de química,227,questão de relações internacionais,6,questão de secretariado executivo,3,questão de sociologia,32,questão de turismo,53,questão de vestibular,3878,questão de zootecnia,29,questão do cefetmg,134,questão do cfc,50,questão do enade,1372,questão do enare,41,questão do encceja,357,questão do enem,765,questão do ifpi,119,questão do ifsul,1,questão do ita,138,questão do revalida,105,questão filosofia,32,questão gs,20,questão idcap,39,questão ioplan,25,questão jornalismo,3,questão mackenzie,1,questão medicina,10,questão nível superior,39,questão nutriçao,74,questão oab,86,questão odontologia,51,questão pedagogia,12,questão psicologia,3,questão publicidade propaganda,3,questão química,54,questão serviço social,30,questão técnico enfermagem,55,questão ucb,1,questão uel,58,questão unesp,60,questões,7147,
ltr
item
Questões com Gabarito: O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação.
O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação.
O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação.
Questões com Gabarito
https://www.questoes.indagacao.com/2022/01/o-problema-p-versus-np-e-um-problema-ainda-nao-resolvido-e-um-dos-mais-estudados-em-computacao.html
https://www.questoes.indagacao.com/
https://www.questoes.indagacao.com/
https://www.questoes.indagacao.com/2022/01/o-problema-p-versus-np-e-um-problema-ainda-nao-resolvido-e-um-dos-mais-estudados-em-computacao.html
true
2441277946171097403
UTF-8
Todas as Postagens Não foram encontradas postagens VEJA TODOS Leia Mais Resposta Cancelar resposta Deletar Por Home PÁGINAS POSTS Veja todos RECOMENDADOS PARA VOCÊ Tudo Sobre ARQUIVOS BUSCAR TODOS OS POSTS >Nenhuma postagem foi encontrada Voltar para Home Domingo Segunda Terça Quarta Quinta Sexta Sábado Dom Seg Ter Qua Qui Sex Sáb Janeiro Fevereiro Março Abril Maio Junio Julho Agosto Setembro Outubro Novembro Dezembro Jan Fev Mar Abr Mai Jun Jul Ago Set Out Nov Dez Agora mesmo 1 minuto atrás $$1$$ minutos agora 1 hora atrás $$1$$ horas atrás Ontem $$1$$ dias atrás $$1$$ semanas atrás mais de 5 semanas atrás Seguidores Seguir CONTEÚDO PREMIUM BLOQUEADO PASSO 1: Compartilhar em uma rede social PASSO 2: Clique no link na sua rede social Copiar todo o código Selecionar todo o código Todos os códigos foram copiados Não é possível copiar os códigos / textos, pressione [CTRL] + [C] para copiar Tabela de conteúdo