๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Time bounded random access machines

โœ Scribed by Stephen A. Cook; Robert A. Reckhow

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
943 KB
Volume
7
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

model for a random access computer, is introduced. A unique feature of the model is that the execution time of an instruction is defined in terms of l(n), a function of the size of the numbers manipulated by the instruction. This model has a fixed program, but it is shown that the computing speeds of this model and a stored-program model can differ by no more than a constant factor. It is proved that

๐Ÿ“œ SIMILAR VOLUMES

A lower time bound for the knapsack prob
A lower time bound for the knapsack problem on random access machines
โœ Peter Klein; Friedhelm Meyer Heide ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 533 KB

a.M. (Fed. Rep.) Summary. We consider random access machines which read the input integer by integer (not bit by bit). For this computational model we prove a quadratic lower bound for the n-dimensional knapsack problem. For this purpose, we combine a method due to Paul and Simon [1] to apply decisi

Feasible Real Random Access Machines
Feasible Real Random Access Machines
โœ Vasco Brattka; Peter Hertling ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 484 KB
Transforming comparison model lower boun
Transforming comparison model lower bounds to the parallel-random-access-machine
โœ Dany Breslauer; Artur Czumaj; Devdatt P. Dubhashi; Friedhelm Meyer auf der Heide ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 758 KB

We provide general transformations of lower bounds in Valiant's parallel-comparison-decision-tree model to lower bounds in the priority concurrent-read concurrent-write parallel-random-access-machine model. The proofs rely on standard Ramsey-theoretic arguments that simplify the structure of the com