Vamos analisar passo a passo o que é necessário para provar que um problema X é NP-completo: 1. Mostrar que X está em NP (ou seja, que uma solução para X pode ser verificada em tempo polinomial). 2. Mostrar que um problema já conhecido como NP-completo pode ser reduzido a X em tempo polinomial. Isso significa que, se conseguirmos resolver X eficientemente, poderemos resolver também o problema NP-completo conhecido, o que indica que X é pelo menos tão difícil quanto esse problema. Agora, analisando as alternativas: a) Incorreta. NP-completude não é demonstrada apenas por experimentos, mas por reduções formais. b) Incorreta. A redução correta é do problema NP-completo conhecido para X, não o contrário. c) Correta. Essa é a definição correta do procedimento para provar NP-completude. d) Incorreta. A direção da redução é fundamental para preservar a dificuldade computacional. e) Incorreta. Mostrar que X pode ser resolvido em tempo polinomial indicaria que X está em P, não que é NP-completo. Portanto, a alternativa correta é: c. Para provar que um problema X é NP-completo, deve-se mostrar que um problema NP-completo conhecido pode ser reduzido a X em tempo polinomial.