On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines
From MaRDI portal
Publication:4732454
DOI10.2307/2274607zbMath0683.03021OpenAlexW4237454406MaRDI QIDQ4732454
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
lower bounddecision treeRAMoraclesalgorithmic problemsRandom Access MachinesBen-Or's lower boundDISJOINT SETSELEMENT DISTINCTNESSSET EQUALITY
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