patternMinor
Are there established complexity classes with real numbers?
Viewed 0 times
realarewithnumbersclassesestablishedtherecomplexity
Problem
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.
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.
Solution
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
-
"transparent" - Only, $O(1)$ to be read,
-
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.
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
-
"transparent" - Only, $O(1)$ to be read,
-
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.
Context
StackExchange Computer Science Q#29567, answer score: 8
Revisions (0)
No revisions yet.