Lower bounds for solving linear diophantine equations on random access machines

DOI10.1145/4221.4250zbMath0633.68031OpenAlexW2064246638MaRDI QIDQ3771611

Friedhelm Meyer auf der Heide

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-5951

zbMATH Keywords

knapsack problemlinear diophantine equationsrandom access machineslinear search algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear Diophantine equations (11D04) Algorithms in computer science (68W99)

Related Items (8)

Lower bound arguments with ``inaccessible numbers ⋮ On the limits of computations with the floor function ⋮ A lower bound for randomized algebraic decision trees ⋮ On genuinely time bounded computations ⋮ On computations with integer division ⋮ Lower bounds on algebraic random access machines ⋮ Simulating probabilistic by deterministic algebraic computation trees ⋮ Generalized finite automata over real and complex numbers

This page was built for publication: Lower bounds for solving linear diophantine equations on random access machines