A complexidade também pode ser vista como uma propriedade do problema, o que significa dar uma medida independente do tratamento dado ao problema, independente do caminho percorrido na busca da solução e, portanto, independente de algoritmos. Alguns problemas são bem-comportados, isto é, permitem chegar a limites de complexidades bem definidos, outros estão em classes com contornos não bem claros. Marque a classe e a definição corretas:

Vamos analisar cada alternativa comparando classe e definição.

A) NP: Por definição, um problema está em NP se, quando a resposta é “Sim”, existe um certificado (testemunha) que pode ser verificado em tempo polinomial por uma máquina de Turing determinística. Isso está correto.

B) NE: NE é a classe dos problemas decidíveis por máquina não determinística em tempo exponencial (tipicamente $2^{O(n)}$), não em tempo polinomial. Logo, falso.

C) R: “R” normalmente se refere a problemas decidíveis (recursivos). “Probabilisticamente polinomial” remete a classes como RP/BPP/PP, não a R. Logo, falso.

D) PP: PP é uma classe probabilística (decisão com probabilidade de acerto > 1/2 em tempo polinomial). “Solúvel em uma quantidade finita de tempo” descreve mais a ideia de decidível/recursivo, não PP. Logo, falso.

E) P: P é tempo polinomial determinístico. “Máquina de Turing não determinística em tempo exponencial com expoente linear” descreve algo como NEXP/NE, não P. Logo, falso.

Portanto, a única combinação correta é a alternativa A.

Alternativa correta: (A).