Lower bounds on algebraic random access machines

DOI10.1007/3-540-60084-1_88MaRDI QIDQ4645192zbMATH OpenOpenAlexFDO

Authors Amir M. Ben-Amram, Zvi Galil

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_88

zbMATH Keywords

knapsack problemrandom access machinecomputation treeelement distinctnessmemory address

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Topological lower bounds on algebraic random access machines
• On the complexity of functions for random access machines
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• Lower bounds for RAMs and quantifier elimination
• Feasible real random access machines

Cites work

• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3499229 (Why is no real title available?)
• scientific article; zbMATH DE number 512852 (Why is no real title available?)
• A lower bound for integer greatest common divisor computations
• 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
• Decision tree complexity and Betti numbers
• Fast exponentiation using the truncation operation
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Lower Bounds for Computations with the Floor Operation
• Lower Bounds for Sorting with Realistic Instruction Sets
• Lower bounds for solving linear diophantine equations on random access machines
• On computations with integer division
• On genuinely time bounded computations

Cited in

(14)

• A problem that is easier to solve on the unit-cost algebraic RAM
• Feasible real random access machines
• A nonlinear lower bound for random-access machines under logarithmic cost
• scientific article; zbMATH DE number 3988710 (Why is no real title available?)
• Lower bounds for dynamic data structures on algebraic RAMs
• Lower bounds for RAMs and quantifier elimination
• scientific article; zbMATH DE number 4119621 (Why is no real title available?)
• Topological lower bounds on algebraic random access machines
• Computing with and without arbitrary large numbers
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• scientific article; zbMATH DE number 4117838 (Why is no real title available?)
• Lower bounds for solving linear diophantine equations on random access machines
• Arbitrary sequence RAMs
• Program algebra for random access machine programs

This page was built for publication: Lower bounds on algebraic random access machines

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