Questões de Teoria da Complexidade

Explore questões resolvidas de Teoria da Complexidade. Acesse respostas e explicações detalhadas para estudar e evoluir.

97% confiança
Para resolver um problema por meios computacionais, é necessário codificá-lo numa dada linguagem e escrever um algoritmo (um programa, nessa mesma linguagem), isto é, um método para resolver o problema num número finito de passos. Um problema é ____ se existe um algoritmo polinomial que o resolva. Se todos os algoritmos conhecidos para resolver um problema forem exponenciais, o problema se diz ______. A alternativa que preenche as lacuna de forma correta é?
algoritmos computacao teoria-da-complexidade
82% confiança
Os problemas de decisão são os mais utilizáveis no dia a dia. Porém, para determinar a carreira da conjectura P ≠ NP, constitui-se um problema de decisão que desafia os cientistas da computação e matemáticos desde seu surgimento. Levando em conta esse problema, considere as seguintes afirmativas. I - Não há problema determinístico de tempo polinomial que solucione esse problema; II - Existem apenas problemas não determinísticos para solucionar esse problema de decisão; III - Existe um algoritmo determinístico de tempo polinomial para esse problema de decisão; IV - Considerando-se, por exemplo, os algoritmos "retorne sim" e "retorne não", um deles será a solução para esse problema de decisão. Quais alternativas estão corretas?
computacao p-vs-np problemas-de-decisao