Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy

DOI10.1006/jcss.2000.1728zbMath0989.65033arXivmath/0005029OpenAlexW2137828924MaRDI QIDQ5943088

J. Maurice Rojas

Publication date: 15 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0005029

zbMATH Keywords

Galois groupsgeneralized Riemann hypothesisdecidabilitypolynomial systemscomputational arithmetic geometryDiophantine problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Computational complexity of sentences over fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetization: A new method in structural complexity theory
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Factoring polynomials with rational coefficients
• On the number of fixed point free elements in a permutation group
• Riemann's hypothesis and tests for primality
• Rational parametrization of surfaces
• Bounds for fixed point free elements in a transitive group and applications to curves over finite fields
• Some speed-ups and speed limits for real algebraic geometry
• Solving degenerate sparse polynomial systems faster
• Algebraic Geometry. I: Complex projective varieties.
• Uncomputably large integral points on algebraic plane curves?
• On the distribution of integer points on curves of genus zero
• An efficient algorithm for the complex roots problem
• On the complexity of diophantine geometry in low dimensions (extended abstract)
• Finding the number of factors of a polynomial
• On Approximation Algorithms for # P
• Computational complexities of diophantine equations with parameters
• Some consequences of the Riemann hypothesis
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Classification of Quantifier Prefixes Over Diophantine Equations
• The Distribution of Galois Groups and Hilbert's Irreducibility Theorem
• Factoring Rational Polynomials over the Complex Numbers
• Every Prime Has a Succinct Certificate
• Fast Multiple-Precision Evaluation of Elementary Functions

This page was built for publication: Computational arithmetic geometry. I: Sentences nearly in the polynomial hierarchy