4
$\begingroup$

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem.

Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

Also, are NP-Hard problems inter-convertible?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ NP-hard problems aren't even necessarily in NP. $\endgroup$
    – chirlu
    Oct 4, 2015 at 22:32

2 Answers 2

Reset to default
5
$\begingroup$

The picture I always visualize for this is the one featured on here on the Wikipedia page for NP-Completeness. The definition of NP-Hard is that it is the set of problems to which all NP problems can be reduced in polynomial time, so, for example, the bounded halting problem - does a Turing Machine $M$ halt within $k$ steps, is strictly not in NP, because there is no way to check in polynomial time whether a Turing Machine halts in $k$ steps. However, all problems can be converted to the bounded halting problem very easily, simply by building a Turing Machine which ostensibly solves the problem and asking whether it halts in some appropriate amount of time.

This answers your first question: not all NP-Hard problems are in NP or can be reduced to them. As for the second: Some NP-Hard problems can be converted to one another. For example, the EXP-TIME class, which can be though of as the next class beyond P, has EXP-TIME-Complete problems just like NP has NP-Complete problems, and there are classes even beyond that, indefinitely.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ "EXP-TIME [...] can be though of as the next class beyond P" Obviously, this is an informal statement which isn't supposed to be literally true but NP, PSPACE and all kinds of other natural classes sit between P and EXP-TIME. EXP-TIME isn't even the smallest class we know to strictly include P: for example, by the time hierarchy theorem, $\mathrm{P}\subsetneq\mathbf{TIME}[n^{O(\log n)}]\subsetneq\mathbf{EXP}$. Also, we don't actually know that NP and EXP-TIME are different, so an EXP-time-complete problem could still be NP-complete. $\endgroup$
    – David Richerby
    Oct 6, 2015 at 9:59
  • $\begingroup$ @DavidRicherby That's true, it's only meant as a mental tool to help you get a hold on the complexity zoo. The reason I like to think of it way way is because it generalizes to EXPTIME=TIME $\left(2^{f(n)}\right) \nsubseteq$ 2-EXPTIME=TIME $\left( 2^{2^{f(n)} } \right) \cdots \nsubseteq k-$ EXPTIME , where in each class you take the union of all polynomial functions $f$. It's a nice first approximation of how hard these problems are, to which you can then relate the more subtle classes. Obviously, the more such tools, the better, so your comments are very helpful. $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 6, 2015 at 10:18
  • $\begingroup$ You mean $\subsetneq$, not $\not\subseteq$. :-) (\subsetneq) $\endgroup$
    – David Richerby
    Oct 6, 2015 at 10:34
  • $\begingroup$ @DavidRicherby Yes, I meant $\subsetneq$, thank you. $\endgroup$
    – Lieuwe Vinkhuijzen
    Oct 6, 2015 at 10:40
  • $\begingroup$ Thank you, the diagram and the example in context help a lot! $\endgroup$
    – Apoorvaa Singh
    Oct 12, 2015 at 3:10
3
$\begingroup$

Can an NP-Hard problem be reduced to an NP problem, which is not already an NP-Complete problem?

No. Suppose that $X$ is NP-hard and it reduces to $Y$. By definition of NP-hardness, every problem in NP reduces to $X$. By transitivity of reduction, every problem in NP also reduces to $Y$, so $Y$ is NP-hard. Since $Y$ is postulated to be in NP, $Y$ is NP-complete.

Also, are NP-Hard problems inter-convertible?

Not necessarily, no. NP-hard problems aren't even necessarily decidable: the halting problem is NP-hard, for example.

For more examples, consider the classes $k$-EXP for integers $k\geq 1$. $1$-EXP is just EXP (exponential time, i.e., time $O(2^n)$), $2$-EXP is problems decidable in time $O(2^{2^n})$, $3$-EXP is triply-exponential $O(2^{2^{2^n}})$ and so on. By the time hierarchy theorem, all of these classes are different, which means that a $k$-EXP-complete problem is not in $(k-1)$-EXP. But a $k$-EXP-complete problem is certainly NP-hard because NP$\,\subseteq\,$EXP$\,\subseteq k$-EXP. So, you can take an infinite sequence $X_1, X_2, \dots$ of problems where $X_i$ is $i$-EXP-complete for each $i$. Each of these problems is NP-hard but $X_k$ is provably not reducible to $X_j$ for any $j<k$.

Improve this answer
$\endgroup$
0

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.