Computing with and without arbitrary large numbers

DOI10.1007/978-3-642-38236-9_17MaRDI QIDQ4922125zbMATH OpenOpenAlexFDO

Authors Michael Brand

Publication date 28 May 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

arbitrary large numbercomplexityinteger RAM

Mathematics Subject Classification ID

Abstract: In the study of random access machines (RAMs) it has been shown that the availability of an extra input integer, having no special properties other than being sufficiently large, is enough to reduce the computational complexity of some problems. However, this has only been shown so far for specific problems. We provide a characterization of the power of such extra inputs for general problems. To do so, we first correct a classical result by Simon and Szegedy (1992) as well as one by Simon (1981). In the former we show mistakes in the proof and correct these by an entirely new construction, with no great change to the results. In the latter, the original proof direction stands with only minor modifications, but the new results are far stronger than those of Simon (1981). In both cases, the new constructions provide the theoretical tools required to characterize the power of arbitrary large numbers.

Recommendations

• Arbitrary sequence RAMs
• P-RAM vs. RP-RAM
• Lower bounds on algebraic random access machines
• scientific article; zbMATH DE number 3850476
• Fast Simulation of Turing Machines by Random Access Machines

Cited in

(4)

• Constant-time sorting
• P-RAM vs. RP-RAM
• scientific article; zbMATH DE number 4132241 (Why is no real title available?)
• Arbitrary sequence RAMs

This page was built for publication: Computing with and without arbitrary large numbers

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