Na teoria da complexidade computacional, problemas podem se...

Com base no mesmo assunto

Ano: 2026 Banca: INSTITUTO AOCP Órgão: IF-CE Prova: INSTITUTO AOCP - 2026 - IF-CE - Professor EBTT - Teoria da Computação |

Q4098358 Algoritmos e Estrutura de Dados

Na teoria da complexidade computacional, problemas podem ser classificados quanto à existência de algoritmos eficientes para sua resolução. É correto afirmar que problemas intratáveis são aqueles

para os quais existem algoritmos determinísticos de tempo polinomial que produzem soluções exatas.

cuja solução pode ser verificada em tempo polinomial, mas que também possuem algoritmos determinísticos conhecidos com esse mesmo limite de tempo.

para os quais não se conhece algoritmo de tempo polinomial, estando frequentemente associados a classes como NP-completo ou NP-difícil.

que admitem paralelização eficiente, podendo ser resolvidos em tempo polilogarítmico com número polinomial de processadores.

cuja solução pode ser obtida em tempo constante por circuitos booleanos de profundidade limitada.

Incorreta. Gabarito oficial da banca:

Treine mais com um simulado focado no seu concurso. Criar simulado

teste

Parabéns! Você acertou!

Está mandando bem! Treine mais em um simulado completo. Criar simulado

teste

🎯 Saiba o que estudar

🎯 Saiba o que estudar

Na teoria da complexidade computacional, problemas podem se...

Questões de assuntos semelhantes

Provas relacionadas