Questão
ID 2010346Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2014 Banca: FUNDEP Gestão de Concursos Órgão: Instituto Federal do Norte de Minas Gerais
Analise as afirmativas referentes à classe de problemas computacionais.
I. Uma linguagem L pertence à classe NP.
II. Uma linguagem L pertence à classe P. III. Toda linguagem L’ pertence à classe NP, L’ é redutível em tempo polinomial a uma linguagem L.
IV. L’ pertence à classe NP. L é redutível em tempo polinomial a uma linguagem L’.
Após sua análise, considerando que uma linguagem L é NP – completa, estão CORRETAS: