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?

$\endgroup$

closed as unclear what you're asking by D.W., Jan Johannsen, Kaveh, András Salamon, Emil Jeřábek supports Monica Feb 7 '18 at 16:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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