On the limits of computations with the floor function

DOI10.1016/0890-5401(88)90031-4MaRDI QIDQ1112603zbMATH OpenOpenAlexFDO

Authors Bettina Just, Friedhelm Meyer auf der Heide, 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) Real-analytic functions (26E05) Topology of special sets defined by functions (54C50) Algorithms in computer science (68W99)

Recommendations

• Lower Bounds for Computations with the Floor Operation
• Publication:4732103
• Curious bounds for floor function sums
• Computability of Fraïssé limits
• On the computation of limsups
• The function \(\lfloor a/m\rfloor\) in sharply bounded arithmetic
• scientific article; zbMATH DE number 2085171
• The limits of fixed-order computation
• The Computational Complexity of Continued Fractions
• On the problem of computing the values of \(L\)-functions

Cites work

• scientific article; zbMATH DE number 3980478 (Why is no real title available?)
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• A lower time bound for the knapsack problem on random access machines
• Approximation to bounded holomorphic functions on strictly pseudoconvex domains
• Lower bounds for solving linear diophantine equations on random access machines
• Lower time bounds for integer programming with two variables

Cited in

(9)

• scientific article; zbMATH DE number 4072374 (Why is no real title available?)
• On the hardness of approximating shortest integer relations among rational numbers
• The PSLQ algorithm for empirical data
• Rational approximations, multidimensional continued fractions, and lattice reduction
• On genuinely time bounded computations
• scientific article; zbMATH DE number 4117838 (Why is no real title available?)
• Fast exponentiation using the truncation operation
• On computations with integer division
• Simulating probabilistic by deterministic algebraic computation trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1112603)