On the Power of Multiplication In Random Access Machines
Original Publication Date: 1974-Sep-30
Included in the Prior Art Database: 2007-Mar-29
Software Patent Institute
Hartmanis, J.: AUTHOR [+3]
7 1/8 x 9 15/16 PRltlT TtIPFFEE FOR 8 1/2 x 11 PACE TO 75% COPY . ..-+ .- ..-- ON THE POWER OF MULTIPLICATION I N IWNDOM ACCESS MACHINES
7 1/8 x 9 15/16 PRltlT TtIPFFEE FOR 8 1/2 x 11 PACE ' TO 75% COPY
- - . -- ..-+ .- ..--
ON THE POWER OF MULTIPLICATION I N IWNDOM ACCESS MACHINES !
Juris XIartmanis I
. - Janos ~imontt
Computer Science Department -
Cornell University Ithaca, N.Y. 14850
j - Abstract
! We consider random access machines with a multiplication operation, having the added capability of computing logical operations on b i t 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 opera- tion as a unit of time and considering the machines as acceptors, deterministic and non- deterministic polynomial time acceptable lan- guages are the same, and are exactly the lan- guages recognizable i n polynomial tape by Turing machines. We observe that the same measure on machines without multiplication is polynomially related t o Turing machine time-- thus the added computational power due t o multiplication in random access machines is equivalent t o the contputational power which polynomrally tape-bounded Turing machine com- putations have over polynomially time-bounded computations. Therefore, i n this formulation, it is not harder to multiply than t o add i f and only i f PTAPE = PTIME for Turing machines. We also discuss other instruction sets for random access machines and their computational power.
be essentially equivalent i f they are polyno- . mially related.*
In the theory of computational complexity one tries to classify problems by the amount
of resources needed t o compute a solution t o the problem by some idealized computer. "~opu- lar" computer models are Turing machines (Tms)
. [lo] and random access machines ( W s ) [ l l ] , and the amount of resource is usually measured by the number of moves o r by the memory used i n the computation. One considers both deter- ministic and nondeterministic models-- in ad- dition, the instruction repertory of a RAM may o r may not contain indirect addressing, addi- tion, multiplication, b i t operations, shifts, etc. Also, it was proposed t o charge an -.-
amount proportional t o the length of the re- gister operated upon for each move of a RAM, instead of a unit cost , 11, Ch. 11. Re- lationships between these models are central problems in computational complexity and, with the exception of the straightforward ones, largely unknown.
In this paper we consider these machines as acceptors. Moreover, a s is customary since 121, we shall pay a l o t of attention t o poly: nomial bounds, and will consider two models t o
,. This research was supported in part by grant 70/755 from Fundaqzo de Amparo h Pesquisa...