Lower bounds for RAMs and quantifier elimination

DOI10.1145/2488608.2488710zbMath1293.68123arXiv1306.0153OpenAlexW2012518989MaRDI QIDQ5495851

Miklós Ajtai

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.0153

zbMATH Keywords

quantifier eliminationlower boundsdiagonalizationRAMnondeterministic computation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantifier elimination, model completeness, and related topics (03C10)

This page was built for publication: Lower bounds for RAMs and quantifier elimination