Browse Prior Art Database

On the Power of Multiplication In Random Access Machines

IP.com Disclosure Number: IPCOM000148359D
Original Publication Date: 1974-Sep-30
Included in the Prior Art Database: 2007-Mar-29
Document File: 14 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Hartmanis, J.: AUTHOR [+3]

Abstract

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

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 14

[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14

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.*

i

    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 [3], 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...