On invariance of degree for certain computations

DOI10.1016/J.JCO.2003.11.007zbMATH Open1161.68478OpenAlexW1964117185MaRDI QIDQ876819FDOQ876819

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

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

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)

Cites Work

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

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)