[Solved]: Are there established complexity classes with real numbers?

ignougroup
Problem Detail: 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.

Asked By : Raphael

Answered By : Kaveh

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.
Best Answer from StackOverflow

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