5. Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA. A união de duas linguagens recursivas é uma lin...
5. Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA.
A união de duas linguagens recursivas é uma linguagem recursiva.
Todo problema que está na classe P também está na classe NP.
Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.
Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva.
Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP.
A Redutibilidade não diz nada em resolver problemas.
A afirmativa I está incorreta.
A afirmativa II está incorreta.
A afirmativa III está incorreta.
A afirmativa IV está incorreta.
A afirmativa V está incorreta.
A união de duas linguagens recursivas é uma linguagem recursiva.
Todo problema que está na classe P também está na classe NP.
Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.
Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva.
Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP.
A Redutibilidade não diz nada em resolver problemas.
A afirmativa I está incorreta.
A afirmativa II está incorreta.
A afirmativa III está incorreta.
A afirmativa IV está incorreta.
A afirmativa V está incorreta.
Essa pergunta também está no material:
💡 1 Resposta
Ed 
A afirmativa VI está incorreta. A Redutibilidade é uma ferramenta importante para resolver problemas em computação, pois permite que um problema seja transformado em outro problema equivalente ou mais simples. A partir daí, é possível aplicar algoritmos já conhecidos para resolver o novo problema.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Perguntas relacionadas
Los trabajos de Kurt Gödel tuvieron una influencia notable en el concepto de la computabilidad y el planteamiento de los problemas que involucran e...
Linguagens de Programação e Estrutura de Dados
Estudando com Questões
Compartilhar