2
$\begingroup$

Basically I am interested in

What is the complexity of numerically solving systems over $\mathbb{R}$?

By solving I mean finding at least one numeric solution with given precision.

Probably the easiest case is the algebraic, but what happens if we throw in $\log,\exp$, trigonometric functions?

Got a potential reduction from solving Diophantine equations to systems with $\arctan,\cot$ over $\mathbb{R}$ (basically $\lfloor x \rfloor = x + \frac{\arctan\left(\cot\left(\pi x\right)\right)}{\pi} - \frac{1}{2}$).

Is it true that numerically solving systems over $\mathbb{R}$ with arithmetic operations and $\arctan, \cot$ is undecidable?

EDIT

According to an answer discontinuous maps are not nice.

Here is another way to force integrality for the reduction from Diophantine equations with continuous maps: to force $x_i$ integral, add equation $\sin{(\pi x_i)}=0$

Improve this question
$\endgroup$
4
  • $\begingroup$ As you say, this is undecidable by reduction to solving Diophantine equations. If $f(x_1, \ldots, x_n)$ is an integer polynomial, then the integer roots of $f$ are the real roots of $f(x_1, \ldots, x_n) + \sum \sin^2 \pi x_i$. $\endgroup$ Commented Oct 2, 2013 at 14:54
  • $\begingroup$ @DavidSpeyer thanks. Asked because in fields stuff is usually easier than in rings IMHO. $\endgroup$ Commented Oct 2, 2013 at 15:06
  • $\begingroup$ True as a rule of thumb, I suppose, but $\sin$ is enough to bring all the hardness you could want. $\endgroup$ Commented Oct 2, 2013 at 15:08
  • $\begingroup$ That should be $f^2+\sum \sin^2 \pi x_i$ above. $\endgroup$ Commented Oct 2, 2013 at 15:09

1 Answer 1

Reset to default
2
$\begingroup$

[Edited on 2013-10-02: see below for answer to the edited version of the question.]

In these sorts of problems it is always better if we know something about the system of equations. At the very least we should have some idea on how continuous the maps are (if they are not continuous then they are not computable and the whole thing is just unreasonable). Next, it is better to try to solve the system only in a bounded area (you can iteratively increase the area if needed).

Let us consider a simple example. Suppose we want to solve $\phi(\vec{x}) = 0$ on a unit cube in $\mathbb{R}^n$ up to precision $\epsilon$ and we know that $\phi$ is Lipschitz with constant $L$. Then we can sample $\phi$ on a grid of points such that no two are more than $\epsilon/L$ apart. We compute the sample values with precision $\epsilon/5$. Either we will find an approximate value $\vec{x}_0$ such that $|f(\vec{x}_0)| < 3\epsilon/5$, in which case we have an approximate solution, or all samples will have absolute values above $2\epsilon/5$ and there is no solution. This is going to be a very dumb and slow method (it is easy to write down Lipschitz functions with a huge $L$), but it is not easy to improve on it.

It really helps if $\phi$ is nice so that sensible numerical methods can be used. But in general the problem "find an $\epsilon$-zero or verify that all values are greater than $\epsilon/2$" is computable.

Answer to the edit in the question: If add the equation $\sin (\pi x_i) = 0$ to force $x_i$ to be integral, then the complexity is still quite horrible. We know that if there is a solution then it must be integral, so this might help us to quickly eliminate any solution that is obviously not integral, but it seems to be that in general complexity remains high.

As an example, consider the above situation of solving $\phi(\vec{x}) = 0$ on the unit cube in $\mathbb{R}^n$. The unit cube has $2^n$ points with integral coordinates. There does not seem to be a general method that will quickly eliminate those points, so naively we will expect complexity to be around $2^n \cdot t(\epsilon)$ where $t(\epsilon)$ is the complexity of evaluating $\phi$ up to precision $\epsilon$.

If we try to solve $\phi(\vec{x}) = 0$ on an unbounded region then the problem is not even computable, because (as you notice yourself) you can encode Diophantine equations in it.

So, if you have a cunning plan is to solve Diophantine equations, you should rethink the situation.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Thank you, will try to edit the question. Can you explain in more detail this: "(if they are not continuous then they are not computable and the whole thing is just unreasonable)". $\tan$ is not continuous but it is certainly computable and has inverse. What about the second question about decidability of hidden floor() (the maps appear computable)? $\endgroup$ Commented Sep 12, 2013 at 11:02
  • 1
    $\begingroup$ $\tan$ is only computable on a domain that does not include any singularity. Since computable here means that you can compute arbitrarily close approximations of the output, given abritrarily close approximations of the input, it follows at once that computable real functions are continuous, as Andrej wrote. $\endgroup$ Commented Sep 12, 2013 at 13:27
  • $\begingroup$ $\tan$ is continuous on its domain of definition. If you insist on viewing it as a map on defined on all of $\mathbb{R}$ then it is still computable, but you need to adjoin an "undefined" value to the real numbers (and get the topology correct). $\endgroup$ Commented Sep 12, 2013 at 13:27
  • 3
    $\begingroup$ floor is not computable because it requires an infinite amount of information to calculate. Imagine a real number whose expansion is 0.999999999.... After how many 9's can you decide what the floor is? The same problem arises with every discontinuity. You could make floor computable if you declared it to be undefined at integer arguments, but that is absurd. $\endgroup$ Commented Sep 12, 2013 at 13:29
  • $\begingroup$ Thanks. According to Wikipedia floor is defined on all of R: en.wikipedia.org/wiki/Floor_and_ceiling_functions $\endgroup$ Commented Sep 12, 2013 at 13:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.