2
$\begingroup$

Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard).

Is there a natural/interesting example of a problem that is known to be $C$ hard, but that the proof of $D$ hardness is significantly different?

For example, $TQBF$ is PSPACE-hard, but proving $NP$-hardness is trivial (by reduction from $SAT$), but I wouldn't consider this example very interesting, as $TQBF$ is a generalization of $SAT$. I am looking for a problem whose natural formulation is e.g. PSPACE hard, but one can show NP-hardness in a different way.

I'm not sure how interesting this question is, but I am curios to see such examples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.