1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ How do you represent this real value in a Turing Machine? Do you work with a model of TM with real numbers? $\endgroup$ – Shaull Aug 19 '14 at 6:59
  • $\begingroup$ @Shaull Thanks I got the point now, I try to find the smallest real number that I need (which is usually $1/polynomial(n)$) and try to add them one-by-one. Thus, it's polynomial. $\endgroup$ – orezvani Aug 19 '14 at 7:12
  • 1
    $\begingroup$ I don't really understand your comment. Please modify the question accordingly, if it's still relevant. $\endgroup$ – Shaull Aug 19 '14 at 7:16
  • 3
    $\begingroup$ You describe neither your problem nor your reduction. How are we supposed to tell, if the reduction is valid? $\endgroup$ – FrankW Aug 19 '14 at 8:15
  • 3
    $\begingroup$ NP is defined via Decision problems on Turing machines. If you have one of those, and you have shown it is in NP, and you have a reduction from an NP-complete problem, then yes your problem is np complete. It doesn't matter whether the input to your Turing machine is encoding integers or real numbers. With that said, there is no encoding of real numbers that you can represent all of them, so I hope you kept that in mind. $\endgroup$ – Kurt Mueller Aug 19 '14 at 8:24
1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As I mentioned (in the comments), the precision is limited to $1/polynomial(n)$, still the problem cannot be classified as NP? $\endgroup$ – orezvani Aug 21 '14 at 0:21
  • 1
    $\begingroup$ @emab I think my answer covers that, implicitly. Show that it's in NP; it may or may not be. We don't know the problem so we can't say. $\endgroup$ – Raphael Aug 21 '14 at 5:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.