<p><a href="https://en.wikipedia.org/wiki/Hilbert&#39;s_tenth_problem" rel="nofollow noreferrer">The Matiyasevich/MRDP</a> Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can be regarded as equal. Therefore, the hardness for finding integral solution to algebraic equations and computational complexity are related, we can charactorize computational complexity based on finding solution to algebraic equations, any reference for this idea? </p>

CC BY-SA 3.0
2018-01-09T16:04:48.570Z
What does this mean: "we can charactorize computational complexity based on finding solution to algebraic equations"?
Sasho Nikolov
CC BY-SA 3.0
2018-01-09T21:02:42.627Z
I think the question is, for example, is there a problem related to finding solutions to algebraic equations that is P-complete (or X-complete where X is any complexity class, either time or space I guess).
Amaury Pouly
CC BY-SA 3.0
2018-01-09T23:32:08.423Z
@AmauryPouly,good example,
XL _At_Here_There
CC BY-SA 3.0
2018-01-09T23:42:59.667Z
Another well known result is the NP-completeness of finding integer solutions to binary quadratics $\alpha x_1^ 2 + \beta x_2 - \gamma = 0$ (K.L.Manders and L.Adleman, NP-complete Decision Problems for Binary Quadratics)
Marzio De Biasi
CC BY-SA 3.0
2018-01-10T00:56:28.220Z
@MarzioDeBiasi, part, hope full reference, and state of art results
XL _At_Here_There
<reference-request><complexity-classes><universal-computation><comp-number-theory><computational-mathematics>
How to charactorize computational complexity based on finding solution to algebraic equations?
XL _At_Here_There
# How to charactorize computational complexity based on finding solution to algebraic equations?

(Asked by: username_0 on 2018-01-09)

[The Matiyasevich/MRDP](https://en.wikipedia.org/wiki/Hilbert's_tenth_problem) Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can be regarded as equal. Therefore, the hardness for finding integral solution to algebraic equations and computational complexity are related, we can charactorize computational complexity based on finding solution to algebraic equations, any reference for this idea?

**Tags:** reference-request, complexity-classes, universal-computation, comp-number-theory, computational-mathematics

> **Comments:**
> **username_1**: What does this mean: "we can charactorize computational complexity based on finding solution to algebraic equations"?  
> **username_2**: I think the question is, for example, is there a problem related to finding solutions to algebraic equations that is P-complete (or X-complete where X is any complexity class, either time or space I guess).  
> **username_0**: @AmauryPouly,good example,  
> **username_3**: Another well known result is the NP-completeness of finding integer solutions to binary quadratics $\alpha x_1^ 2 + \beta x_2 - \gamma = 0$ (K.L.Manders and L.Adleman, NP-complete Decision Problems for Binary Quadratics)  
> **username_0**: @MarzioDeBiasi, part, hope full reference, and state of art results  

---

## 0 answers

