On the complexity of \(p\)-adic basic semi-algebraic sets

DOI10.1016/j.jco.2006.09.003zbMath1119.03035OpenAlexW1974634297MaRDI QIDQ883331

Jennifer Whitehead, Michael Maller

Publication date: 4 June 2007

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2006.09.003

zbMATH Keywords

complexity\(p\)-adic numbers\(p\)-adic analogues of semi-algebraic setsbasic semi-algebraic setsMacintyre predicatesroots of \(p\)-adic polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Complexity of computation (including implicit computational complexity) (03D15) Semialgebraic sets and related spaces (14P10) Other nonanalytic theory (11S85) Polynomials (11S05)

Cites Work

• Unnamed Item
• Unnamed Item
• The geometric theory of \(p\)-adic fields
• The complexity of elementary algebra and geometry
• Computational complexity over the \(p\)-adic numbers
• Efficient \(p\)-adic cell decompositions for univariate polynomials
• On definable subsets of p-adic fields
• Bounds on transfer principles for algebraically closed and complete discretely valued fields
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: On the complexity of \(p\)-adic basic semi-algebraic sets