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.

  • 1
    $\begingroup$ For 1., one definition I know uses in place of a real number $\alpha$ a computable function $g : \mathbb{N} \rightarrow \mathbb{Q}$ such that $|g(k) - \alpha| \le \frac{1}{k} \forall k$. $\endgroup$ – Cocopuffs Jun 27 '12 at 13:18
  • $\begingroup$ Retagged, I'm not sure "real analysis" is appropriate for this question. $\endgroup$ – Cocopuffs Jun 27 '12 at 13:20
  • $\begingroup$ It's good to cite the paper where you found this statement so the context is understood. I suspect the context is using a model of computation for real or complex arithmetic where arbitrary such operands can be added, multiplied, etc. in fixed time. Simplified thus the computational complexity comes down to counting the number of arithmetic (or elementary function) operations required. $\endgroup$ – hardmath Jun 27 '12 at 13:29
  • $\begingroup$ I added a link to the paper. It is a rather algebraic context. What you say is, concerning my first follow-up question, equivalent to extending the alphabet to $\mathbb F$ and adding special states for adding and multiplying two cells to the set of states of the turing machine, right? $\endgroup$ – born Jun 27 '12 at 13:37
  • $\begingroup$ @born: Yes, it would be equivalent to that. Of course your emphasis on Turing machines is probably not in the spirit of the paper (thanks for adding the link). But solving linear equations "in exact arithmetic" has $O(n^3)$ complexity where $n$ counts both the equations and unknowns. $\endgroup$ – hardmath Jun 27 '12 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.