Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq337486
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
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
  1. AI e II.
  2. BI e IV.
  3. CI, II e III.
  4. DII, III e IV
  5. EIII e IV.
Revelar gabarito e comentário

GabaritoB — I e IV.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Transformações Polinomiais (Reduções)

Gabarito: letra B. Estão corretas apenas as afirmativas I e IV. A afirmativa I é verdadeira porque toda redução polinomial deve ser computável por uma Máquina de Turing determinística em tempo polinomial (definição clássica). A afirmativa IV é verdadeira pois, embora o espaço usado possa ser polinomial, é possível ("pode") que seja limitado por uma constante – o enunciado não exige que sempre o seja, apenas admite a possibilidade. As demais afirmativas incorrem em erros conceituais sobre o significado de redução.

Item I — ✅ Correto

A definição de redução polinomial (Karp reduction) exige que exista uma função computável por uma Máquina de Turing determinística em tempo polinomial. Sem essa exigência, a redução não seria eficiente e não poderia ser usada para demonstrar NP-dificuldade.

Item II — ❌ Incorreto

A redução mapeia elementos de A (strings de A) para elementos de B, mas isso não implica que a linguagem A seja um subconjunto de B. As linguagens podem ter alfabetos diferentes ou a transformação pode alterar a representação. Exemplo: a redução de SAT para 3-SAT mapeia fórmulas booleanas para fórmulas em 3-CNF, mas fórmulas SAT genéricas não estão contidas em 3-SAT (pois 3-SAT é um subconjunto restrito).

Item III — ❌ Incorreto

Se A pertence a NP e existe uma redução polinomial de A para B, então B é NP-difícil (ou NP-completo se também estiver em NP), mas não se pode garantir que B pertença a NP. A redução transfere a dificuldade (hardness), não a certificação. Por exemplo, pode-se reduzir SAT (que está em NP) ao Problema da Parada (que é indecidível e, portanto, não está em NP).

Item IV — ✅ Correto

A afirmação usa o verbo "pode" (poder), indicando possibilidade, não obrigatoriedade. De fato, existem reduções que usam espaço constante (ex.: uma redução que apenas adiciona um prefixo fixo). Embora reduções polinomiais possam usar espaço polinomial, isso não impede que existam reduções de espaço constante. Logo, a afirmativa é verdadeira.

Gabarito: letra B – apenas os itens I e IV estão corretos.

Link permanente: /questoes/qq337486