3
$\begingroup$

The Matiyasevich/MRDP 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?

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ What does this mean: "we can charactorize computational complexity based on finding solution to algebraic equations"? $\endgroup$ – Sasho Nikolov Jan 9 '18 at 16:04
  • 1
    $\begingroup$ 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). $\endgroup$ – Amaury Pouly Jan 9 '18 at 21:02
  • $\begingroup$ @AmauryPouly,good example, $\endgroup$ – XL _At_Here_There Jan 9 '18 at 23:32
  • 2
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Jan 9 '18 at 23:42
  • $\begingroup$ @MarzioDeBiasi, part, hope full reference, and state of art results $\endgroup$ – XL _At_Here_There Jan 10 '18 at 0:56