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?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What does this mean: "we can charactorize computational complexity based on finding solution to algebraic equations"? $\endgroup$– Sasho NikolovJan 9, 2018 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 PoulyJan 9, 2018 at 21:02
-
$\begingroup$ @AmauryPouly,good example, $\endgroup$– XL _At_Here_ThereJan 9, 2018 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 BiasiJan 9, 2018 at 23:42
-
$\begingroup$ @MarzioDeBiasi, part, hope full reference, and state of art results $\endgroup$– XL _At_Here_ThereJan 10, 2018 at 0:56
Add a comment
|