Lower bound arguments with ``inaccessible numbers

DOI10.1016/0022-0000(88)90032-3zbMath0652.68039OpenAlexW1486395995MaRDI QIDQ1107308

Martin Dietzfelbinger, Wolfgang Maass

Publication date: 1988

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(88)90032-3

zbMATH Keywords

Shortest pathparallel random access machinesKnapsacklinear decision treesMinimum perfect matchingTraveling salesperson

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Lower bounds for sorting of sums

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• On the complexity of computations under varying sets of primitives
• Simulation of Parallel Random Access Machines by Circuits
• Trade-Offs between Depth and Width in Parallel Computation
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Lower bounds for solving linear diophantine equations on random access machines
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines

This page was built for publication: Lower bound arguments with ``inaccessible numbers