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.


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.