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?

O enunciado faz referência ao grande problema em torno da conjectura P ≠ NP, que, em termos de problema de decisão, costuma ser entendida como a questão: “P = NP?” (responder SIM ou NÃO).

Vamos analisar as afirmativas:

I - Não há problema determinístico de tempo polinomial que solucione esse problema.

Aqui “esse problema” é o problema de decisão P = NP?. Se existisse um algoritmo determinístico em tempo polinomial que decidisse corretamente P = NP?, isso resolveria definitivamente a questão. Como não se conhece tal algoritmo (o problema permanece em aberto), em contexto de prova essa afirmativa é tomada como correta no sentido de “não há (conhecido) algoritmo determinístico polinomial que resolva o problema”.

II - Existem apenas problemas não determinísticos para solucionar esse problema de decisão.

Isso está incorreto. O problema “P = NP?” não é “solucionado” por “problemas não determinísticos”; ele é uma pergunta meta-teórica sobre classes de complexidade. Além disso, mesmo para problemas NP, não é correto dizer que “apenas” o não determinismo resolve — há problemas em NP que também estão em P (logo, determinísticos polinomiais).

III - Existe um algoritmo determinístico de tempo polinomial para esse problema de decisão.

Isso implicaria que já existe um procedimento eficiente que decide corretamente “P = NP?” e, portanto, que a questão estaria resolvida. Como não existe algoritmo conhecido que faça isso, a afirmativa é falsa no contexto usual.

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.

Essa é verdadeira: como a pergunta “P = NP?” tem apenas duas respostas possíveis (SIM ou NÃO), então um algoritmo constante que sempre responda “SIM” ou sempre responda “NÃO” coincidirá com a resposta correta em um dos dois mundos possíveis. O ponto é que não sabemos qual deles é o correto.

Logo, estão corretas I e IV.

Alternativa correta: (b).