On the limits of computations with the floor function

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

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

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 functionsreal functionfloor functionmeasurable setsalgebraic computation treesdecidable languagesanalytic computation treehalting

Mathematics Subject Classification ID

Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Topology of special sets defined by functions (54C50) Real-analytic functions (26E05) Algorithms in computer science (68W99)

Related Items

Fast exponentiation using the truncation operation ⋮ On genuinely time bounded computations ⋮ The PSLQ algorithm for empirical data ⋮ On computations with integer division ⋮ On the hardness of approximating shortest integer relations among rational numbers

Cites Work

• 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
• Unnamed Item

This page was built for publication: On the limits of computations with the floor function