HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Can NP-Hard be converted to NP?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canhardconverted

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#47869, answer score: 5

Revisions (0)

No revisions yet.