4
$\begingroup$

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle):

For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb F$ the solutions of $ \sum_{i=1}^na_ix_i^2=b$ can be found in deterministic polynomial time.

My base-question is: What exactly is meant by finding a solution over reals in deterministic polynomial time?

I have the following follow-up questions and thoughts/suggestions:

  1. What exactly is meant by giving real or complex numbers as the input to an algorithm / a turing machine?

    Normally the alphabet of a turing machine is finite and the input is a finite word in this alphabet. I see different approaches:

    1. We can assume that $b$ and $a_i$ are represented in a finite way. For example as a rational number which is a pair of integers. This whould be perfect for me but restricts the set of inputs dramatically from an uncountable set to a countable one.
    2. We can also give $b$ and $a_i$ as a finite term in some symbols like $\sqrt{2}$ and $\pi$. But if we want to maintain the finiteness of the alphabet, we can only use finitely many of such symbols which doesn't help in the general case. In this approach we also restrict the size of the input set as above.
    3. We can assume that the alphabet itself is $\mathbb F$. But I think such a turing machine is very powerful, since it should also be able to add or multiply two cells in one step, allowing an infinite number of calculations in only one step (i.e. multiply $\pi$ with $2$).

    Which of this representations is the most common one? I think we have to restrict ourselfs to a countable set of inputs if we want to maintain the nature of a turing machine. Or am I missing something?

  2. What can I expect as an output? / What is the algorithm?

    1. Here the situation is even worse then above: Even if we are in approach 1 to give the input, the output could also be something like $\sqrt 2$ (choose $n=1, a_1=1, b=2$).
    2. Of course I'm aware of Newton's method to solve the above equation but this algorithm only converges and not necessarily gives an exact result after a finite number of steps. Should I also give an error bound as input and say that a "solution" is a solution up to a difference of this bound? Another problem with Newton's method is that it may not converge at all (the derivative can become zero for example). This may be solved by choosing a feasible starting point, but it couldn't be chosen at random because the statements speaks of deterministic polynomial time.

Thank you very much in advance for any help or input.

  • 0
    @born: I don't know if this is relevant to what your paper is talking about, but so-called *exact real arithmetic* has been a popular research are the past few years. You might take a look at [this HaskellWiki page](http://www.haskell.org/haskellwiki/Exact_real_arithmetic) and [this portal page at Imperial College](http://wwwhomes.doc.ic.ac.uk/~ae/exact-computation/) to see if it's related. If so, those pages will have links to more fundamental papers.2012-06-28

0 Answers 0