///
Esta questão foi aplicada no ano de 2018 pela banca FCM no concurso para IFN-MG. A questão aborda conhecimentos da disciplina de Estruturas de Dados e Algoritmos, especificamente sobre Teoria dos Algoritmos, Análise de Complexidade.
Esta é uma questão de múltipla escolha com 5 alternativas. Teste seus conhecimentos e selecione a resposta correta.
Uma transformação polinomial é uma ferramenta fundamental na demonstração de que determinado problema é NP-difícil.
Avalie as afirmações sobre propriedades que transformações polinomiais devem satisfazer.
I. Para toda transformação polinomial, deve existir uma Máquina de Turing determinística que a computa em tempo polinomial.
II. Se uma transformação polinomial transforma um elemento de linguagem A em um elemento de linguagem B, então A é um subconjunto não necessariamente próprio de B.
III. Se uma transformação polinomial transforma um elemento de uma linguagem A em um elemento de linguagem B, e A pertence a NP, então B pertence a NP.
IV. A quantidade de espaço utilizada pela transformação pode ser limitada por uma constante.
Está correto apenas o que se afirma em