Generic complexity of the Diophantine problem

DOI10.1515/GCC-2013-0004MaRDI QIDQ2873316zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov

Publication date 23 January 2014

Published in Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/gcc-2013-0004

zbMATH Keywords

Diophantine equationgeneric complexityHilbert's tenth problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Diophantine equations in many variables (11D72) Decidability (number-theoretic aspects) (11U05)

Recommendations

• On generic undecidability of Hilbert's tenth problem for polynomial trees
• On generic complexity of the discrete logarithm problem
• On generic complexity of the validity problem for Boolean formulas
• On generic NP-completeness of the Boolean satisfiability problem
• Generic undecidability of universal theories

Cited in

(13)

• Generic amplification of recursively enumerable sets
• On the complexity of Diophantine geometry in low dimensions (extended abstract)
• scientific article; zbMATH DE number 4112574 (Why is no real title available?)
• ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
• On generic complexity of the validity problem for Boolean formulas
• On generic complexity of the discrete logarithm problem
• ON GENERIC COMPLEXITY OF DECIDABILITY PROBLEM FOR DIOPHANTINE SYSTEMS IN THE SKOLEM’S FORM
• On generic undecidability of Hilbert's tenth problem for polynomial trees
• On generic complexity of the problem of representation of natural numbers by sum of two squares
• The generic complexity of the bounded problem of graphs clustering
• The generic complexity of the graph triangulation problem
• On the generic complexity of solving equations over natural numbers with addition
• The complexity of almost linear diophantine problems

This page was built for publication: Generic complexity of the Diophantine problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2873316)