On the complexity of p-adic basic semi-algebraic sets

DOI10.1016/J.JCO.2006.09.003zbMATH Open1119.03035OpenAlexW1974634297MaRDI QIDQ883331FDOQ883331

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) Polynomials (11S05) Number-theoretic algorithms; complexity (11Y16) Semialgebraic sets and related spaces (14P10) Complexity of computation (including implicit computational complexity) (03D15) Other nonanalytic theory (11S85)

Cites Work

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

Cited In (3)

• Classification of semi-algebraic \(p\)-adic sets up to semi-algebraic bijection
• Semilinear cell decomposition
• On the complexity of a putative counterexample to the -adic Littlewood conjecture

Recommendations

• On the complexity of a putative counterexample to the -adic Littlewood conjecture 👍 👎
• On the structure of semialgebraic sets over p-adic fields 👍 👎
• p-adic semi-algebraic sets and cell decomposition. 👍 👎
• Basicness of semialgebraic sets 👍 👎
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets 👍 👎
• On two notions of complexity of algebraic numbers 👍 👎
• Computational complexity over the \(p\)-adic numbers 👍 👎
• Complexity of stratifications of semi-Pfaffian sets 👍 👎
• The Semisimplicity Problem for p-Adic Group Algebras 👍 👎
• Counting complexity classes for numeric computations II 👍 👎

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

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