On the power of multiplication in random access machines
- 1 October 1974
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 13-23
- https://doi.org/10.1109/swat.1974.20
Abstract
We consider random access machines with a multiplication operation, having the added capability of computing logical operations on register are considered both as an integer and as a vector of bits and both arithmetic and boolean operations may be used on the same register. We prove 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 polynomial tape by Turing machines. We observe that the same measure on machines without multiplication is polynomially related to Turing machine time-thus the added computational power due to multiplication in random access machines is equivalent to the computational power which polynomially tape-bounded Turing machine computations have over polynomially time-bounded computations. Therefore, in this formulation, it is not harder to multiply than to add if and only if PTAPE = PTIME for Turing machines. We also discuss other instruction sets for random access machines and their computational power.Keywords
This publication has 8 references indexed in Scilit:
- A characterization of the power of vector machinesPublished by Association for Computing Machinery (ACM) ,1974
- Predecessor machines and regressing functionsPublished by Association for Computing Machinery (ACM) ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Form and Content in Computer Science (1970 ACM turing lecture)Journal of the ACM, 1970
- On the minimum computation time of functionsTransactions of the American Mathematical Society, 1969
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Computability of Recursive FunctionsJournal of the ACM, 1963