A opção correta é: "R é NP-Completo." Explicação: - Sabemos que S é NP-Completo e que Q é tempo polinomial redutível a S, o que significa que Q é pelo menos tão difícil quanto S. - Além disso, sabemos que S é tempo polinomial redutível a R, o que significa que S é pelo menos tão fácil quanto R. - Portanto, se R não fosse pelo menos tão difícil quanto S, então Q seria redutível a R e, portanto, estaria em NP, o que contradiz a informação dada de que Q não está em NP. - Assim, concluímos que R é pelo menos tão difícil quanto S, o que significa que R é NP-Completo.
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar