-1
$\begingroup$

And if so would this grant us any insight into the relations between P, NP, and EXPTIME?

$\endgroup$
4
$\begingroup$

We already know that NP is included in EXPTIME. So every NP problem can not only be reduced to an EXPTIME problem: it is an EXPTIME problem!

$\endgroup$
2
$\begingroup$

Any problem having an EXPTIME algorithm can be reduced to an EXPTIME problem, namely the problem itself (the reduction maps the input to itself). Every problem in NP has an EXPTIME algorithm, so every problem in NP can be reduced to some EXPTIME problem in polynomial time.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.