Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Na teoria da complexidade computacional, problemas podem ser classificados quanto à exi...
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
A
para os quais existem algoritmos determinísticos de tempo polinomial que produzem soluções exatas.
B
cuja solução pode ser verificada em tempo polinomial, mas que também possuem algoritmos determinísticos conhecidos com esse mesmo limite de tempo.
C
para os quais não se conhece algoritmo de tempo polinomial, estando frequentemente associados a classes como NP-completo ou NP-difícil.
D
que admitem paralelização eficiente, podendo ser resolvidos em tempo polilogarítmico com número polinomial de processadores.
E
cuja solução pode ser obtida em tempo constante por circuitos booleanos de profundidade limitada.