# Are there any problems which are known to be both NP-complete and EXPTIME-complete?

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$$.

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$$

• 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! Aug 9, 2022 at 1:26
• I suppose that's true, yes. Aug 9, 2022 at 4:04