Blum–Shub–Smale model of computation
E537367
The Blum–Shub–Smale model of computation is a theoretical framework for analyzing algorithms over real numbers, extending classical complexity theory beyond discrete computation.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Blum–Shub–Smale model of computation canonical | 1 |
| Blum–Shub–Smale model of real computation | 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
NERFINISHED
ⓘ
real RAM model NERFINISHED ⓘ |
| 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
NERFINISHED
ⓘ
P_R NERFINISHED ⓘ complexity classes over the reals ⓘ decision problems over the reals ⓘ |
| extends |
classical Turing machine model
NERFINISHED
ⓘ
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" NERFINISHED ⓘ |
| 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
NERFINISHED
ⓘ
Mike Shub NERFINISHED ⓘ Steve Smale NERFINISHED ⓘ |
| 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
NERFINISHED
ⓘ
algebraic complexity theory ⓘ computable analysis ⓘ real RAM NERFINISHED ⓘ |
| 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
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Blum–Shub–Smale model of computation Description of subject: The Blum–Shub–Smale model of computation is a theoretical framework for analyzing algorithms over real numbers, extending classical complexity theory beyond discrete computation.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Blum–Shub–Smale model of real computation