Diophantine complexity

DOI10.1007/BF01098277MaRDI QIDQ2276953zbMATH OpenOpenAlexFDO

Authors Yu. Matiyasevich

Publication date 1991

Published in Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01098277

zbMATH Keywords

complexity measuresDavis normal formdiophantine complexityDiophantine representationexponential Diophantine representationrecursively enumerable setsurvey

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Diophantine equations (11D99)

Review text

[For the entire collection see Zbl 0657.00011.] See the review in Zbl 0679.03016.

Cites work

• A Machine-Independent Theory of the Complexity of Recursive Functions
• An unsolvable problem in number theory
• Arithmetical problems and recursively enumerable predicates
• Arithmetical representation of recursively enumerable sets
• Decidability of some Problems Pertaining to Base 2 Exponential Diophantine Equations
• scientific article; zbMATH DE number 3539209 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• NP-complete decision problems for binary quadratics
• On the Number of Solutions of Diophantine Equations
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• Some representations of Diophantine sets
• The decision problem for exponential diophantine equations
• Uniform normal form for general time-bounded complexity classes
• Universal diophantine equation

Cited in

(1)

• scientific article; zbMATH DE number 4112574 (Why is no real title available?)

This page was built for publication: Diophantine complexity

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