Questão de Não definido — Geral — INSTITUTO AOCP 2026
Não definidoGeral
- Código
- qg725904
- Banca
- INSTITUTO AOCP
- Órgão
- IF-CE
- Ano
- 2026
- Nível
- Superior
- Cargo
- Professor EBTT - Teoria da Computação
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
- Apara os quais existem algoritmos determinísticos de tempo polinomial que produzem soluções exatas.
- Bcuja solução pode ser verificada em tempo polinomial, mas que também possuem algoritmos determinísticos conhecidos com esse mesmo limite de tempo.
- Cpara os quais não se conhece algoritmo de tempo polinomial, estando frequentemente associados a classes como NP-completo ou NP-difícil.
- Dque admitem paralelização eficiente, podendo ser resolvidos em tempo polilogarítmico com número polinomial de processadores.
- Ecuja solução pode ser obtida em tempo constante por circuitos booleanos de profundidade limitada.