Blum–Shub–Smale model of computation

E537367

complexity theory framework computational model theoretical model

The Blum–Shub–Smale model of computation is a theoretical framework for analyzing algorithms over real numbers, extending classical complexity theory beyond discrete computation.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (7)

Label	Occurrences
Blum–Shub–Smale machine	2
Blum–Shub–Smale model of computation canonical	2
"On a theory of computation and complexity over the real numbers"	1
Blum–Shub–Smale computational model	1
Blum–Shub–Smale model of real computation	1
Smale–Shub model of computation	1
Smale–Shub model of computation over the reals	1

How this entity was disambiguated

This entity first appeared as the object of triple T5645006 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Blum–Shub–Smale model of computation
Context triple: [Lenore Blum, notableWork, Blum–Shub–Smale model of computation]

A. Computing with Register Machines
"Computing with Register Machines" is a chapter in the classic computer science textbook *Structure and Interpretation of Computer Programs* that introduces low-level machine models and shows how higher-level language constructs can be implemented using simple register-based operations.
B. Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
C. The Calculus of Computation
The Calculus of Computation is a textbook that introduces the mathematical foundations of verification, focusing on logic-based methods for specifying and proving properties of computational systems.
D. arithmetization of syntax
Arithmetization of syntax is a method in mathematical logic that encodes formal language expressions and proofs as natural numbers so that syntactic properties can be studied using arithmetic.
E. Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Blum–Shub–Smale model of computation
Target entity description: The Blum–Shub–Smale model of computation is a theoretical framework for analyzing algorithms over real numbers, extending classical complexity theory beyond discrete computation.

A. Computing with Register Machines
"Computing with Register Machines" is a chapter in the classic computer science textbook *Structure and Interpretation of Computer Programs* that introduces low-level machine models and shows how higher-level language constructs can be implemented using simple register-based operations.
B. Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
C. The Calculus of Computation
The Calculus of Computation is a textbook that introduces the mathematical foundations of verification, focusing on logic-based methods for specifying and proving properties of computational systems.
D. arithmetization of syntax
Arithmetization of syntax is a method in mathematical logic that encodes formal language expressions and proofs as natural numbers so that syntactic properties can be studied using arithmetic.
E. Furst–Saxe–Sipser lower bounds
Furst–Saxe–Sipser lower bounds are foundational results in circuit complexity theory that established superpolynomial lower bounds for constant-depth Boolean circuits (AC⁰), demonstrating inherent limitations of such circuits for computing certain functions.
F. None of above. chosen

Statements (47)

Predicate	Object
instanceOf	complexity theory framework ⓘ computational model ⓘ theoretical model ⓘ
alsoKnownAs	BSS model ⓘ real RAM model ⓘ
assumes	unit-cost arithmetic operations on real numbers ⓘ
characterizedBy	focus on algebraic operations rather than bit operations ⓘ unit-time cost for each arithmetic operation ⓘ
contrastsWith	bit-level Turing machine model ⓘ
defines	NP_R ⓘ P_R ⓘ complexity classes over the reals ⓘ decision problems over the reals ⓘ
extends	classical Turing machine model ⓘ linked to: Turing machine discrete complexity theory ⓘ
field	computational complexity theory ⓘ numerical analysis ⓘ real computation ⓘ theoretical computer science ⓘ
formalizedIn	"On a theory of computation and complexity over the real numbers" ⓘ linked to: Blum–Shub–Smale model of computation
hasApplication	computational geometry ⓘ optimization over the reals ⓘ real algebraic geometry ⓘ
hasFeature	branching based on sign of real-valued tests ⓘ infinite precision real arithmetic ⓘ random-access memory of real registers ⓘ
namedAfter	Lenore Blum ⓘ Mike Shub ⓘ Steve Smale ⓘ linked to: Stephen Smale
operatesOn	real numbers ⓘ vectors of real numbers ⓘ
purpose	analyze algorithms over real numbers ⓘ generalize computation beyond discrete structures ⓘ study complexity of real-valued computations ⓘ
relatedTo	Turing machine ⓘ algebraic complexity theory ⓘ computable analysis ⓘ real RAM ⓘ
supportsOperation	addition on real numbers ⓘ comparison of real numbers ⓘ division on real numbers ⓘ multiplication on real numbers ⓘ subtraction on real numbers ⓘ
usedFor	analyzing geometric algorithms ⓘ analyzing numerical algorithms abstractly ⓘ studying feasibility of systems of polynomial equations ⓘ
yearProposed	late 1980s ⓘ

How these facts were elicited