patternMinor
NP-hardness of an optimization problem with real value
Viewed 0 times
realproblemhardnesswithvalueoptimization
Problem
I have an optimization problem, whose answer is a real value, not an integer such as vertex cover and set cover. Therefore, the decision version of my problem is given an input and a real value $r$.
I have been able to reduce an NP-complete problem to my own problem in polynomial time. I also showed that my problem is NP.
Since the input to the decision problem is a real value, is this reduction valid and can I categorize my problem as NP-complete?
Edit: What if the precision of this real number is limited to $\frac{1}{polynomial(n)}$, which means that the solution is a real number with a polynomial precision.
I have been able to reduce an NP-complete problem to my own problem in polynomial time. I also showed that my problem is NP.
Since the input to the decision problem is a real value, is this reduction valid and can I categorize my problem as NP-complete?
Edit: What if the precision of this real number is limited to $\frac{1}{polynomial(n)}$, which means that the solution is a real number with a polynomial precision.
Solution
No, you can not say that your problem is NP-complete.
The reason is that it is not in NP: there is no Turing machine at all (let alone a poly-time (non-deterministic) one) that can solve it because TMs can not handle real numbers.
The reduction may still go through and show that the problem is NP-hard; a subset of the reals should certainly suffice to model the naturals in Vertex Cover or whatever NP-complete problem you use. So it is, in principle, possible to define a computable, poly-time reduction function that does the job. It will output naturals (or integers, rationals, ...), of course, but as long as you are willing to accept these as real numbers you are fine.
This reduction is likely to carry over to restricted versions of your problem (e.g. finite precision) which can be classified in the framework of computabilty/complexity theory.
The reason is that it is not in NP: there is no Turing machine at all (let alone a poly-time (non-deterministic) one) that can solve it because TMs can not handle real numbers.
The reduction may still go through and show that the problem is NP-hard; a subset of the reals should certainly suffice to model the naturals in Vertex Cover or whatever NP-complete problem you use. So it is, in principle, possible to define a computable, poly-time reduction function that does the job. It will output naturals (or integers, rationals, ...), of course, but as long as you are willing to accept these as real numbers you are fine.
This reduction is likely to carry over to restricted versions of your problem (e.g. finite precision) which can be classified in the framework of computabilty/complexity theory.
Context
StackExchange Computer Science Q#29227, answer score: 3
Revisions (0)
No revisions yet.