Separation of complexity classes in Koiran's weak model
type: Item
instance of: scholarly article
title: Separation of complexity classes in Koiran's weak model
zbMATH Open document ID: 0819.68053
DOI: 10.1016/0304-3975(94)00069-7
author: Michael Shub
author: Felipe Cucker
author: Stephen Smale
published in: Theoretical Computer Science
publication date: 1994-11-27T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 695888
zbMATH Keywords: complexity classes
Wikidata QID: Q57733307
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)00069-7
OpenAlex ID: W2030220007
cites work: Q3692867
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q3770650
cites work: \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
cites work: On the Complexity of Quantifier Elimination: the Structural Approach
cites work: On digital nondeterminism
cites work: Real quantifier elimination is doubly exponential
cites work: Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
cites work: Turing machines that take advice
cites work: Computing over the reals with addition and order
cites work: A note on a \(P \neq NP\) result for a restricted class of real machines
cites work: On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: Q4131648
DBLP publication ID: journals/tcs/CuckerSS94
description: scientific article; zbMATH DE number 695888