¿Existe algún problema decidible que NO sea NP-HARD?

Question

¿Hay alguna prueba de que existe un problema decidible que NO sea NP-HARD?

Answer 1

La respuesta es muy sencilla:

Ya que necesita uno $x \in A$ y una $x \not \in A$ para una reducción en tiempo polinómico, $A = \emptyset$ no puede ser un lenguaje difícil para NP.