On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines

DOI10.2307/2274607zbMath0683.03021OpenAlexW4237454406MaRDI QIDQ4732454

Wolfgang Maass

Publication date: 1988

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2274607

zbMATH Keywords

lower bounddecision treeRAMoraclesalgorithmic problemsRandom Access MachinesBen-Or's lower boundDISJOINT SETSELEMENT DISTINCTNESSSET EQUALITY

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (4)

P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\) ⋮ Tables should be sorted (on random access machines) ⋮ Lower bound arguments with ``inaccessible numbers ⋮ Meanders and their applications in lower bounds arguments

This page was built for publication: On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines