On the limits of computations with the floor function

DOI10.1016/0890-5401(88)90031-4zbMath0659.68051MaRDI QIDQ1112603

László Babai, Friedhelm Meyer auf der Heide, Bettina Just

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90031-4

zbMATH Keywords

analytic functions; real function; floor function; measurable sets; algebraic computation trees; decidable languages; analytic computation tree; halting

Mathematics Subject Classification ID

28A05: Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets

54C50: Topology of special sets defined by functions

26E05: Real-analytic functions

68W99: Algorithms in computer science

Related Items

On the hardness of approximating shortest integer relations among rational numbers, Fast exponentiation using the truncation operation, On computations with integer division

Cites Work

• Unnamed Item
• A lower time bound for the knapsack problem on random access machines
• Lower time bounds for integer programming with two variables
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Approximation to bounded holomorphic functions on strictly pseudoconvex domains
• Lower bounds for solving linear diophantine equations on random access machines