On the Power of Multiplication in Random Access Machines
| dc.contributor.author | Simon, Janos | en_US |
| dc.date.accessioned | 2007-04-19T19:07:59Z | |
| dc.date.available | 2007-04-19T19:07:59Z | |
| dc.date.issued | 1974-04 | en_US |
| dc.description.abstract | We consider random access machines with a multiplication operation, having the added capability of computing logical operations on bit vectors in parallel. The contents of a 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 a Turing machine. We observe that the same measure on machines without multiplication is polynomially related to Turing machine time - thus the power of multiplication on this model characterizes the difference between Turing machine tape and time measures. We discuss other instruction sets and their power. | en_US |
| dc.format.extent | 1759900 bytes | |
| dc.format.extent | 871033 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-205 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6045 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | On the Power of Multiplication in Random Access Machines | en_US |
| dc.type | technical report | en_US |