3
$\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$
8
  • 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, 2014 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, 2014 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, 2014 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, 2014 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$ Aug 19, 2014 at 8:24

3 Answers 3

2
$\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$
2
  • $\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, 2014 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, 2014 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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