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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 42, 230–265 (1936)
Ben-Amram, A.M., Galil, Z.: On the power of the shift instruction. Inf. Comput. 117, 19–36 (1995)
Bshouty, N.H., Mansour, Y., Schieber, B., Tiwari, P.: Fast exponentiation using the truncation operation. Comput. Complexity 2(3), 244–255 (1992)
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., Reading (1975); Second printing, Addison-Wesley Series in Computer Science and Information Processing
Mansour, Y., Schieber, B., Tiwari, P.: Lower bounds for computations with the floor operation. SIAM J. Comput. 20(2), 315–327 (1991)
Brand, M.: Does indirect addressing matter? Acta Inform. 49(7-8), 485–491 (2012)
Simon, J., Szegedy, M.: On the complexity of RAM with various operation sets. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 624–631. ACM, New York (1992)
Simon, J.: Division in idealized unit cost RAMs. J. Comput. System Sci. 22(3), 421–441 (1981); Special issue dedicated to Michael Machtey
Trahan, J.L., Loui, M.C., Ramachandran, V.: Multiplication, division, and shift instructions in parallel random-access machines. Theor. Comp. Sci. 100(1), 1–44 (1992)
Schönhage, A.: On the power of random access machines. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol. 71, pp. 520–529. Springer, Heidelberg (1979)
Hartmanis, J., Simon, J.: On the power of multiplication in random access machines. In: 15th Annual Symposium on Switching and Automata Theory, pp. 13–23. IEEE Comput. Soc., Long Beach (1974)
Simon, J.: On feasible numbers (preliminary version). In: Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), pp. 195–207. Assoc. Comput. Mach., New York (1977)
Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci. 4, 177–192 (1970)
Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. Assoc. Comput. Mach. 26(2), 361–381 (1979)
Radó, T.: On non-computable functions. Bell System Tech. J. 41, 877–884 (1962)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brand, M. (2013). Computing with and without Arbitrary Large Numbers. In: Chan, TH.H., Lau, L.C., Trevisan, L. (eds) Theory and Applications of Models of Computation. TAMC 2013. Lecture Notes in Computer Science, vol 7876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38236-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-38236-9_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38235-2
Online ISBN: 978-3-642-38236-9
eBook Packages: Computer ScienceComputer Science (R0)