On invariance of degree for certain computations

DOI10.1016/J.JCO.2003.11.007MaRDI QIDQ876819zbMATH OpenOpenAlexFDO

Authors Michael Maller

Publication date 30 April 2007

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

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

zbMATH Keywords

BSS machinescontinuous computational complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational aspects and applications of commutative rings (13P99)

Recommendations

• P\(\neq\) NC over the \(p\)-adic numbers
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• scientific article; zbMATH DE number 1956513
• Specified precision polynomial root isolation is in NC
• On the parallel arithmetic complexity of the root-finding problem

Cites work

• scientific article; zbMATH DE number 953031 (Why is no real title available?)
• scientific article; zbMATH DE number 3288410 (Why is no real title available?)
• Computational complexity over the \(p\)-adic numbers
• Lower Bounds in a Parallel Model without Bit Operations
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On definable subsets of p-adic fields
• P\(\neq\) NC over the \(p\)-adic numbers
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)

This page was built for publication: On invariance of degree for certain computations

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