Simon, Janos2007-04-192007-04-191974-04http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-205https://hdl.handle.net/1813/6045We 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.1759900 bytes871033 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report