On the Power of Multiplication in Random Access Machines

Juris Hartmanis, Janoš Šimon · Scandinavian Workshop on Algorithm Theory · 1974

Summary

It is proved that, counting one operation as a unit of time and considering the machines as acceptors, deterministic and nondeterministic polynomial time acceptable languages are the same, and are exactly the languages recognizable in polynomially tape by Turing machines.

Type: article
Published: 1974-04-01
Cited by: 98
References: 10
Access: Open access
DOI: https://doi.org/10.1109/swat.1974.20
OpenAlex: https://openalex.org/W1987540368
Semantic Scholar: https://api.semanticscholar.org/CorpusID:10071187

Keywords

Turing machine, Time hierarchy theorem, Non-deterministic Turing machine, NSPACE, Computer science

References

Review: Alan Cobham, Yehoshua Bar-Hillel, The Intrinsic Computational Difficulty of FunctionsS. Cook — 1969
Relationships Between Nondeterministic and Deterministic Tape ComplexitiesWalter J. Savitch — 1970
A characterization of the power of vector machinesVaughan Pratt, Michael O. Rabin, Larry J. Stockmeyer — 1974
ON THE MINIMUM COMPUTATION TIME OF FUNCTIONSStephen Cook, Stål Aanderaa — 1969
Form and Content in Computer Science (1970 ACM turing lecture)Marvin Minsky — 1970
Predecessor machines and regressing functionsJohn C. Warkentin, Patrick C. Fischer — 1972
The complexity of theorem-proving proceduresStephen Cook — 1971
Computability of Recursive FunctionsJ. C. Shepherdson, Howard E. Sturgis — 1963
Hierarchies of memory limited computationsRichard E. Stearns, Juris Hartmanis, Philip Lewis — 1965
The Intrinsic Computational Difficulty of FunctionsCobham, Alan, Bar-Hillel, Yehoshua — 1969
Form and Content in Computer ScienceM. Minsky — 1972

Cited by

Computational complexity of an optical model of computationDamien Woods — 2005
On the complexity of numerical analysisEric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen — 2006
Computing with arbitrary and random numbersMichael Brand — 2017
Logic and complexity of synchronous parallel computationsStanisław Radziszowski — 1978
Models for Parallel Computation in Multi-Core, Heterogeneous, and Ultra Wide-Word ArchitecturesAlejandro Salinger — 2013
The RAM equivalent of P vs. RPMichael Brand — 2013
Machine models and linear time complexityKenneth W. Regan — 1993
A Canonical Form of Vector MachinesKazuo Iwama, Chuzo Iwamoto — 1998
On Tape-Bounded Probabilistic Turing Machine AcceptorsJanoš Šimon — 1981
A characterization of the power of vector machinesVaughan Pratt, Michael O. Rabin, Larry J. Stockmeyer — 1974
On the complexity of RAM with various operation setsJanoš Šimon, Márió Szegedy — 1992
Parallel random access machines with powerful instruction setsWalter J. Savitch — 1981
Measuring 4-local qubit observables could probabilistically solve PSPACEPaweł Wocjan, Dominik Janzing, Thomas Decker — 2003
Division in Idealized Unit Cost RAMSJanoš Šimon — 1981
Universal circuits (Preliminary Report)Leslie G. Valiant — 1976
Parallelism in random access machinesSteven Fortune, James Wyllie — 1978
A unified approach to models of synchronous parallel machinesLeslie M. Goldschlager — 1978
Array processing machines: An abstract modelJan Van Leeuwen, Jiřı́ Wiedermann — 1987
On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machinesWolfgang Maass — 1988
On Live-Dead Analysis for Global Data Flow ProblemsLawrence T. Kou — 1977

On the Power of Multiplication in Random Access Machines

Summary

Keywords

References

Cited by

Related papers