NP-hardness of an optimization problem with real value

Question

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.

Answer 1

Yes, you can categorize your problem as in NP and is NP-complete if you have the followings:

• The set of real numbers from which you draw the number from and you use as input into your procedure is countable

In this case, you can represent your input as proper input into Turing machine because you can encode any countable set. Remember that a union of a finite number of countable sets is still a countable set.

To be more concrete, for example, if your real numbers are restricted to something like the set of all rational numbers $Q$ (countable) union with the set of all $\sqrt{x}$ where $x \in Q$, then you still have countable set (you can add $\sqrt[3](x)$, $sin(x)$, $log(x)$, etc.. as long as the number of them is finite). Your problem is still in NP and is NP-complete even though the numbers are real numbers.

Nevertheless, as the previous answer points out, if your real numbers form a smooth set, then it is another case which will be very interesting to think further.

Answer 2

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.

Answer 3

The book Complexity and Real Computation extended the Turing machine and extensively discussed the computational complexity problem for algorithms involving real numbers. For example, the authors extend the concept of NP to such algorithms.