Grátis: Observe a figura a seguir: Existe um problema S qualquer que é NP-Completo. Existem outros dois problemas Q e R que não estão em NP, e onde Q é tem... – Questões Respondidas

Método Científico

Outros

Observe a figura a seguir: Existe um problema S qualquer que é NP-Completo. Existem outros dois problemas Q e R que não estão em NP, e onde Q é tempo polinomial redutível a S e S é tempo polinomial redutível a R.
Considerando as informações apresentadas, assinale a opção correta.
A+
A
A- R é NP-Hard.
Q é NP-Hard.
Q e R são NP-Completo.
Q é NP-Completo.
R é NP-Completo.

Perguntas sobre Metodologia Científica

há 3 dias

Perguntas sobre Metodologia Científica

há 3 dias

Teste_ Atividade Objetiva 3 2 tentativa

Teste_ Atividade Objetiva 3 2 tentativa

FAM

Respostas

Ed

há 3 dias

Para resolver essa questão, vamos analisar as definições e as relações entre os problemas S, Q e R. 1. Problema S: É NP-Completo, o que significa que é um problema que está em NP e que todos os problemas em NP podem ser reduzidos a ele em tempo polinomial. 2. Problema Q: É redutível a S em tempo polinomial. Isso significa que Q é, pelo menos, tão difícil quanto S. Como S é NP-Completo, isso implica que Q é NP-Hard. 3. Problema R: S é redutível a R em tempo polinomial. Isso significa que R é, pelo menos, tão difícil quanto S. Portanto, R também é NP-Hard. Agora, vamos analisar as alternativas: - A+: R é NP-Hard. (Correto, pois S é redutível a R) - A: Q é NP-Hard. (Correto, pois Q é redutível a S) - A-: Q e R são NP-Completo. (Incorreto, pois Q e R não estão em NP) - Q é NP-Completo. (Incorreto, pois Q não está em NP) - R é NP-Completo. (Incorreto, pois R não está em NP) Dessa forma, as opções A+ e A estão corretas, mas como a questão pede para assinalar a opção correta, a resposta mais direta e que se encaixa no contexto é: A: Q é NP-Hard.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Teste_ Atividade Objetiva 3 2 tentativa

Teste_ Atividade Objetiva 3 2 tentativa

FAM

Mais perguntas desse material

Leia o texto a seguir: Quanto tempo leva para executar um determinado algoritmo? Os cientistas da computação não dão a resposta em minutos ou milissegundos; eles a dão em relação ao número de instruções que o algoritmo tem que manipular.
Considerando as informações apresentadas, avalie as afirmacoes a seguir: I. Seja X um problema que pertence à classe NP, logo, se X é NP-Hard, então ele é NP-Completo. II. O problema de determinar se existe um ciclo em um grafo não direcionado está em P. III. Se quisermos provar que um problema X é NP-Hard, precisamos primeiramente provar que ele é um NP-Completo. É correto o que se afirma em:
I e II, apenas.
II, apenas.
III, apenas.
I e III, apenas.
II e III, apenas.

Leia o texto a seguir: A complexidade de tempo refere-se a quantas etapas são necessárias para resolver um problema e como o número de etapas necessárias aumenta com o tamanho do problema. Dado um algoritmo, a Complexidade de Tempo do algoritmo é descrita como uma função assintótica que depende do tamanho de entrada do algoritmo.
Considerando as informações apresentadas, avalie as afirmações a seguir: I. De acordo com o tamanho de entrada, podemos distinguir os algoritmos em função de complexidade polinomial, os quais são chamados de eficientes. II. Existem muitos problemas computacionais impossíveis de serem resolvidos em tempo polinomial; eles são chamados de NP ou Não-Polinomial. III. Alguns problemas computacionais estão na classe NP-Hard e esses são classificados como pelo menos tão difíceis quanto os problemas mais difíceis em NP. É correto o que se afirma em:
A+
A
A- II e III, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
II, apenas.

Leia o texto a seguir: A busca é o processo no qual um algoritmo encontra a sequência de várias etapas necessárias para resolver um determinado problema, sendo necessariamente de dois tipos: busca cega (desinformada) ou busca heurística (busca informada). Em inteligência artificial, por exemplo, uma busca informada fornece mais eficiência.
Considerando as informações apresentadas, avalie as seguintes asserções e a relação proposta entre elas. I. A busca informada pode resolver o problema além da definição da função, assim como pode encontrar a solução de forma mais eficiente. PORQUE II. Apesar de possuir conhecimento prévio, o estado meta (objetivo) pode ser alcançado usando diferentes ordens e duração das ações. A respeito dessas asserções, assinale a opção correta:
A+
A
A- Salvo em 10:04
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são ambas proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Leia o texto a seguir: Dada uma grade de Sudoku incompleta (famoso jogo baseado na colocação lógica de números), desejamos saber se ela possui pelo menos uma solução válida. Qualquer solução de Sudoku proposta pode ser facilmente verificada, e o tempo para verificar uma solução cresce de forma polinomial à medida que a grade aumenta.
Qual propriedade melhor descreve a solução dessa classe de problema?
O problema de decisão Sudoku está em NP se suas soluções podem ser verificadas de forma eficiente.
O problema de decisão Sudoku é um problema categorizado como NP, o qual é um conjunto da classe P.
O problema do jogo Sudoku está na classe NP, logo, também é da classe P, uma vez que NP é uma classe de problemas dentro de P.
O Sudoku é resolvido em um tempo P, onde P é o conjunto de todos os problemas de decisão que são solucionáveis com eficiência.
O problema do jogo Sudoku está na classe de algoritmos Polinomiais, logo, são chamados de eficientes.