2
$\begingroup$

Are there any problems which are known to be both NP-complete and EXPTIME-compelte? My guess is no, because we know that $P$ is not equal to $EXPTIME$ and EXPTIME-complete problems are not in $P$, and hence a problem that was both NP-complete and EXPTIME-complete would imply $P \not= NP$. Is my thinking correct?

Note that in a difference in notation, here $EXPTIME=EXP$.

$\endgroup$

1 Answer 1

3
$\begingroup$

No, that is not currently known. If such a problem were known, it would prove that:

$$NP=EXPTIME$$

Incidentally, it would also prove that $NP=PSPACE$, because it is known that:

$$P \subseteq NP \subseteq PSPACE \subseteq EXPTIME$$

We don't know which of these subset relations are strict subset relations, but at least one of them must be, because by the time hierarchy theorem:

$$P \subset EXPTIME$$

$\endgroup$
2
  • 1
    $\begingroup$ So just to verify, from what you stated this would imply $P \not= NP$ since we need a strict subset, and since NP and PSPACE and EXPTIME would all be equal, this would mean that the only possible strict subset is P is a strict subset of NP? Thanks for the answer! $\endgroup$
    – user918212
    Aug 9, 2022 at 1:26
  • $\begingroup$ I suppose that's true, yes. $\endgroup$
    – Pseudonym
    Aug 9, 2022 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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