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

DOI10.2307/2274607zbMath0683.03021MaRDI 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 bound; decision tree; RAM; oracles; algorithmic problems; Random Access Machines; Ben-Or's lower bound; DISJOINT SETS; ELEMENT DISTINCTNESS; SET EQUALITY

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03D15: Complexity of computation (including implicit computational complexity)

03D10: Turing machines and related notions

Related Items

Lower bound arguments with ``inaccessible numbers, Meanders and their applications in lower bounds arguments, P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\)