Cheap and Secure Web Hosting Provider : See Now

[Solved]: NP-hardness of an optimization problem with real value

, , No Comments
Problem Detail: 

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.

Asked By : emab

Answered By : InformedA

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29227

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback