Há problemas computacionais que aparentam ser extremamente simples, porém têm alto nível de abstração e complexidade envolvidas em sua solução. É c...

Vamos analisar cada afirmativa: 1. A redutibilidade entre problemas é uma técnica utilizada com eficiência em algoritmos difíceis para indicar a natureza polinomial. - Esta afirmativa está incorreta. A redutibilidade entre problemas é uma técnica utilizada para mostrar a complexidade de um problema em relação a outro, não necessariamente para indicar a natureza polinomial. - Portanto, a afirmativa é falsa. 2. É razoável afirmar que as classes de problemas P e NP-completo são partes da classe de problema NP, de acordo com teóricos. - Esta afirmativa está correta. A classe P está contida na classe NP, e os problemas NP-completos são os mais difíceis da classe NP. - Portanto, a afirmativa é verdadeira. 3. Diz-se que um certificado em problemas de decisão é a prova cabal de que tal problema está em P e ao mesmo tempo em NP-completo. - Esta afirmativa está incorreta. Um problema estar em P e NP-completo ao mesmo tempo é altamente improvável, pois implicaria que P = NP, o que é um dos maiores problemas em aberto na teoria da computação. - Portanto, a afirmativa é falsa. 4. Em complexidade de algoritmos em grafo, um problema difícil é aquele que não tem um tempo polinomialmente determinístico. - Esta afirmativa está correta. Um problema difícil em complexidade de algoritmos em grafo é aquele que não pode ser resolvido em tempo polinomial determinístico. - Portanto, a afirmativa é verdadeira. Com base na análise acima, a sequência correta é: B. V – F – V – F.