Diophantine complexity
From MaRDI portal
Publication:2276953
DOI10.1007/BF01098277zbMath0724.03027OpenAlexW4253533019MaRDI QIDQ2276953
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
surveyrecursively enumerable setcomplexity measuresDiophantine representationDavis normal formdiophantine complexityexponential Diophantine representation
Complexity of computation (including implicit computational complexity) (03D15) Diophantine equations (11D99)
Cites Work
- Unnamed Item
- Unnamed Item
- Uniform normal form for general time-bounded complexity classes
- The decision problem for exponential diophantine equations
- NP-complete decision problems for binary quadratics
- Arithmetical representation of recursively enumerable sets
- An unsolvable problem in number theory
- Universal diophantine equation
- Reduction of an arbitrary diophantine equation to one in 13 unknowns
- On the Number of Solutions of Diophantine Equations
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Some representations of Diophantine sets
- Arithmetical problems and recursively enumerable predicates
- Decidability of some Problems Pertaining to Base 2 Exponential Diophantine Equations