Transfer theorems via sign conditions

DOI10.1016/S0020-0190(01)00197-1zbMath1032.68086MaRDI QIDQ1603522

Pascal Koiran

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Computational complexityPolynomial hierarchyAlgebraic complexitySign conditionsTransfer theorems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
• A weak version of the Blum, Shub, and Smale model
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Definability and fast quantifier elimination in algebraically closed fields
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Feedforward nets for interpolation and classification
• A note on a \(P \neq NP\) result for a restricted class of real machines
• Computing over the reals with addition and order: Higher complexity classes
• Learnability and the Vapnik-Chervonenkis dimension
• On the Power of Real Turing Machines over Binary Inputs
• On the combinatorial and algebraic complexity of quantifier elimination
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

This page was built for publication: Transfer theorems via sign conditions