MO640 - Questão para a prova oral

Número: 017

A definição de algorítmos que podem ser classificados na classe NP é:

a) algorítmos cujo número de passos cresce exponêncialmente com o tamanho da entrada

b) algorítmos que não podem ser resolvidos em tempo polinomial

c) algorítmos que tem a propriedade que diz que se um algorítmo X é redutível a ele, então X é redutível a todos os outros algorítmos da mesma classe.

d) Algorítmos que podem ser resolvidos em tempo polinomial em uma máquina não determinística.

e) N. D. A.