14
$\begingroup$

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:

I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one reduction), so $P$ is NP-hard.

My answer was basically:

Since $P$ has instances with values from $\mathbb{R}$, it's trivially not Turing-computable so you can skip the reduction.

While formally true, I don't think this approach is insightful: we'd certainly like to be able to capture the "inherent complexity" of a real-valued decision (or optimisation) problem, ignoring the limitations we face in dealing with real numbers; investigating these issues is for another day.

It is, of course, not always as easy as saying, "the discrete version of Subset Sum is NP-complete, so the continuous version is 'NP-hard' as well". In this case, the reduction is easy but there are famous cases of the continuous version being easier, e.g. linear vs. integer programming.

It occurred to me that the RAM model naturally extends to real numbers; let every register store a real number and extend the basic operations accordingly. The uniform cost model still makes sense -- as much as in the discrete case, anyway -- while the logarithmic one does not.

So, my question boils down to: are there established notions of complexity of real-valued problems? How do they relate to the "standard" discrete classes?

Google searches yield some results, e.g. this, but I have no way of telling what is established and/or useful and what is not.

$\endgroup$
  • 1
    $\begingroup$ You might find interesting "Complexity and Real Computation" amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/… $\endgroup$ – Kurt Mueller Sep 1 '14 at 13:43
  • $\begingroup$ It seems to me that your answer to your student was unwarranted for one simple reason: Whatever computation we are used to view as based on the reals can be conducted as well using computable reals. I do not know whether this is an answer that is usable for the purpose of your student, but it should at least do away with the lack of Turing computability argument. Unfortunately, I am not expert enough on these issues to develop this further. $\endgroup$ – babou Sep 4 '14 at 22:47
  • $\begingroup$ @babou As far as computability goes, that may be a reasonable restriction (but one they would have to state nonetheless!). However, what happens with complexity? $\endgroup$ – Raphael Sep 5 '14 at 7:55
  • $\begingroup$ @Raphael My point is actually that it is not even a restriction, and need not be stated. It is simply unavoidable. The only reals you can consider in a computation are the computable reals (Church-Turing Thesis). The nice part is apparently that it does not change any of the relevant mathematics, with proper care. Going beyond the computable reals is, like using higher levels of the Turing hierarchy, fascinating speculation, with probably little impact on anything real (pun unavoidable). $\endgroup$ – babou Sep 5 '14 at 19:43
8
$\begingroup$

Yes. There are.

There is the real-RAM/BSS model mentioned in the other answer. The model has some issues and AFAIK there is not much research activity about it. Arguably, it is not a realistic model of computation.

The more active notion of real computability is that of higher type computation model. The basic idea is that you define complexity for higher type functions and then use higher type functions to represent real numbers.

The study of complexity of higher type functions goes back to at least to [ 1 ]. For recent work check Akitoshi Kawamura papers on complexity of real operators.

The classical reference for complexity of real functions is Ker-I Ko's book [ 2 ]. The 6th chapter the more recent book by Klause Weihrauch [ 3 ] also discusses complexity of real comptation (but it is more focused on computability than a complexity).

  • [ 1 ] Stephen Cook and Bruce Kapron, "Characterizations of the basic feasible functionals of finite type", 1990.

  • [ 2 ] Ker-I Ko, "Computational Complexity of Real Functions", 1991.

  • [ 3 ] Klaus Weihrauch' "Computable Analysis", 2000.

$\endgroup$
  • $\begingroup$ What makes the higher type function model more realistic than the real RAM model? $\endgroup$ – Raphael Sep 22 '14 at 14:51
  • 1
    $\begingroup$ @Raphael, I think I explained it in the linked question. If you want a more through treatment there are several, one is chapter 9 of Weirauch. IIRC, another good one is an article by Tucker and Stolenberg-Hansen. $\endgroup$ – Kaveh Sep 22 '14 at 19:00
  • 1
    $\begingroup$ In my view the real-RAM model has two main problems: on one hand it lacks the notion of arbitrary precision rational approximation of real numbers which is arguably their main property, on the other hand it allows comparison of real numbers which AFAIK no one knows how to do in practice. As a result some real functions that we consider efficiently computable in practice are not computable in the model, while some efficiently computable real functions in the model are not computable at all in practice. $\endgroup$ – Kaveh Sep 22 '14 at 19:13
  • $\begingroup$ @Kaveh I am bothered by the imprecision of the whole discussion, in the question and in the answers. Are we talking of traditional uncountable reals, or of the computable reals. From your last comment, you are talking of "real functions that we consider efficiently computable in practice", so I tend to believe it is about computable reals. What do you actually mean? $\endgroup$ – babou Apr 19 '15 at 13:16
8
$\begingroup$

The model you describe is known as the Blum-Shub-Smale (BSS) model (also Real RAM model) and indeed used to define complexity classes.

Some interesting problems in this domain are the classes $P_R$, $NP_R$, and of course the question of whether $P_R$ = $NP_R$. By $P_R$ we mean the problem is polynomially decidable, $NP_R$ is the problem is polynomially verifiable. There are hardness/completeness questions about the class $NP_R$. An example of an $NP_R$ complete problem is the the problem of $QPS$, Quadratic Polynomial System, where the input is real polynomials in $m$ variables, and $p_1, ..., p_n$ $\subseteq$ $R[x_1, ..., x_n]$ of degree at most 2, and each polynomial has at most 3 variables. The question whether there is a common real solution $R^n$, such that $p_1(a), p_2(a), ... p_n(a) = 0$. This is an $NP_R$ complete problem.

But more interestingly there has been some work on the relationship between $PCP$,(Probalistically Checkable Proofs), over the Reals, ie the class $PCP_R$, and how it relates to the algebraic computation models. The BSS model pans to all of $NP$ over reals. This is standard in literature, and what we know today is that $NP_R$ has "transparent long proofs", and "transparent short proofs". By "transparent long proofs" the following is implied: $NP_R$ is contained in $PCP_R(poly, O(1))$. There is also an extension which says, the the "Almost (approximated) Short Version" is true too. Can we stabilize the proof and detect faults by inspecting considerably less many (real) components than $n$? This leads to questions about existence of zeros for (system of) univariate polynomials given by straight line program. Also, by "transparent long proofs" we mean

  1. "transparent" - Only, $O(1)$ to be read,

  2. long - superpolynomial number of real components.

The proof is tied to $3SAT$, and sure one way to look at real valued problems is how it might be related to Subset Sum - even approximation algorithms for the real valued problems would be interesting -as for optimization - Linear Programming we know is in the class $FP$,but yes it would be interesting to see how approximatability might impact the completeness/ hardness for the case of $NP_R$ problems. Also, another question would be the $NP_R$ $=$ $co\text{-}NP_R$?

While thinking of the class $NP_R$, there are counting classes also defined to allow for reasoning about polynomial arithmetic. While $\#P$ is the class of functions $f$ defined over $\{0,1\}^\infty$ $\rightarrow$ $\mathbb{N}$ for which there exists a polynomial time Turing machine $M$ and a polynomial $p$ with the property that $\forall n $$\in$$ \mathbb{N}$, and $x$$\in$$\{0,1\}^{n}$, $f(x)$ counts the number of strings $y \in$$\{0,1\}^{p(n)}$that the Turing Machine $M$ accepts $\{x,y\}$. For reals we extend this idea there are additive BSS machines - BSS machines that do only addition, and multiplications (no divisions, no subtractions). With additive BSS machines(nodes in computation only allow addition, and multiplication) the model for $\# P$ becomes one in which the count is over the vectors that the additive BSS machines accepts. So, the counting class is $\#P_{add}$ this class is useful in the study of Betti numbers, and also the Euler characteristic.

$\endgroup$
  • $\begingroup$ The real-RAM(Random Access Machine), or BSS(Blum-Shub-Smale) machine is the model, mentioned earlier is widely accepted as norm for reasoning about these classes. $\endgroup$ – user3483902 Sep 22 '14 at 14:55
  • $\begingroup$ No, that claim is absolutely false. E.g. have a look at CCA-Net and see how many researchers are using that model. $\endgroup$ – Kaveh Sep 22 '14 at 19:09
  • $\begingroup$ Well, the models used for the complexity classes in the post use the BSS model, and as time progresses there may be other models, do those other models work with the complexity classes in the post? BTW, the comment was a clarification about the models used in the classes in concern, which the post addressed, so there was no clarification as to whether there other models. Again, the clarification was about the models used in the classes, there was no claim. $\endgroup$ – user3483902 Sep 22 '14 at 22:32

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.