3
$\begingroup$

Need to know the relation between EXPTIME and NP HARD complexity classes.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Actually the wiki articles are not telling that, that is why I posted this question. $\endgroup$ – Gradient Aug 10 '16 at 6:11
  • $\begingroup$ For all your "whats the relation of complexity class A to class B" questions, the Complexity Zoo is the comprehensive resource. $\endgroup$ – adrianN Aug 10 '16 at 7:31
  • 1
    $\begingroup$ @DavidRicherby Bah, I was thinking NP complete, my bad completely. $\endgroup$ – jmite Aug 10 '16 at 15:54
7
$\begingroup$

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, however, and NP-complete is of course contained in NP.

$\endgroup$
  • $\begingroup$ Heh. You beat me to it because I did more typing. :-) $\endgroup$ – David Richerby Aug 10 '16 at 8:01
7
$\begingroup$

The two classes are incomparable: neither is a subset of the other.

  • There are problems in EXPTIME that are not NP-hard. The languages $\emptyset$ and $\Sigma^*$ are both in EXPTIME but are definitely not NP-hard since no other language can be many-one reduced to either of them. If we assume that P$\,\neq\,$NP, then we get plenty more problems (all of P) that are in EXPTIME but not NP-hard.

  • There are NP-hard problems that are not in EXPTIME. For example, consider the class 2EXPTIME$\,=\bigcup_{c\geq 0}\mathrm{TIME}\left[2^{2^{n^c}}\right]$. Because NP$\,\subset\,$2EXPTIME any 2EXPTIME-complete problem is NP-hard. However, by the time hierarchy theorem, we know that EXPTIME$\,\neq\,$2EXPTIME, which means that no problem in EXPTIME is 2EXPTIME-complete. (In fact, for a more extreme example, the halting problem is NP-hard and that's definitely not in EXPTIME!)

$\endgroup$
  • $\begingroup$ Can someone provide me with a link where it is explained how the empty language is in EXPTIME like stated above? Wouldn't solving this problem mean solving the halting problem, as a turing machine that accepts this language would never stop? $\endgroup$ – Gasp0de Mar 2 '17 at 14:14
  • $\begingroup$ @Gasp0de You need to familiarize yourself with the definitions. Deciding a language doesn't mean finding a string that's in it: it just means having an algorithm that takes a string as an input and tells you whether or not the given string is in the language. In the case of the empty language, it just says "no" for every string. You can say "no" in a single computation step, which is certainly no more than $2^{(\text{length of string})^k}$. $\endgroup$ – David Richerby Mar 2 '17 at 16:05
  • $\begingroup$ @DavidRicherby I am unable to understand why NP is a proper subset of 2EXPTIME leads to "Any 2EXPTIME-complete problem is NP-hard". Any 2EXPTIME-complete problem is in 2EXPTIME and any 2EXPTIME language can be reduced to it. I am having difficulty in what has it got to do with NP-hardness. NP-hard languages can be anywhere outside NP. A little hint would suffice. $\endgroup$ – Pawan Kumar Jun 1 '17 at 12:07
  • 1
    $\begingroup$ @PawanKumar Because if any 2EXPTIME-complete problem was in NP, then every problem in 2EXPTIME would be in NP, too, so we'd have 2EXPTIME=NP. But we know that 2EXPTIME≠NP. $\endgroup$ – David Richerby Jun 1 '17 at 14:04
-3
$\begingroup$

NP hard is a subset of EXPTIME, but we have no idea if that subset is strict. Answered by: @jmite

$\endgroup$
  • 1
    $\begingroup$ Incorrect. Any 2EXPTIME-complete problem is NP-hard but is not in EXPTIME $\endgroup$ – David Richerby Aug 10 '16 at 7:51

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.