4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. Actually the wiki articles are not telling that, that is why I posted this question. $\endgroup$
    – Gradient
    Aug 10, 2016 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, 2016 at 7:31
  • 1
    $\begingroup$ @DavidRicherby Bah, I was thinking NP complete, my bad completely. $\endgroup$ Aug 10, 2016 at 15:54

3 Answers 3

9
$\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$
1
  • $\begingroup$ Heh. You beat me to it because I did more typing. :-) $\endgroup$ Aug 10, 2016 at 8:01
8
$\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$
4
  • $\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, 2017 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$ Mar 2, 2017 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$ Jun 1, 2017 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$ Jun 1, 2017 at 14:04
-4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Incorrect. Any 2EXPTIME-complete problem is NP-hard but is not in EXPTIME $\endgroup$ Aug 10, 2016 at 7:51

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.