Lower bound arguments with ``inaccessible numbers

DOI10.1016/0022-0000(88)90032-3zbMATH Open0652.68039OpenAlexW1486395995MaRDI QIDQ1107308FDOQ1107308

Authors: 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

Recommendations

• scientific article; zbMATH DE number 3988710
• On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
• Lower bounds for Z-numbers
• scientific article; zbMATH DE number 3985202
• Lower bounds for arithmetic problems
• Numbers with integer complexity close to the lower bound
• A lower bound for approximating the Grundy number
• Lower bounds for the numerical radius
• Lower bounds for the numerical radius
• scientific article; zbMATH DE number 2101286

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)

Cites Work

• Title not available (Why is that?)
• Simulation of Parallel Random Access Machines by Circuits
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the complexity of computations under varying sets of primitives
• Trade-Offs between Depth and Width in Parallel Computation
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• 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
• Title not available (Why is that?)
• 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

Cited In (4)

• There's No Forcing a Least Upper Bound
• Lower time bounds for solving linear diophantine equations on several parallel computational models
• Lower bounds for sorting of sums
• Title not available (Why is that?)

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

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