✦ LIBER ✦

Feasible Real Random Access Machines

✍ Scribed by Vasco Brattka; Peter Hertling

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 484 KB
Volume: 14
Category: Article
ISSN: 0885-064X
DOI: 10.1006/jcom.1998.0488

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Time bounded random access machines

✍ Stephen A. Cook; Robert A. Reckhow 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 943 KB

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 o

Random access machines with multi-dimens

Random access machines with multi-dimensional memories

✍ J.M. Robson 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 183 KB

Computational complexity of random acces

Computational complexity of random access stored program machines

✍ J. Hartmanis 📂 Article 📅 1971 🏛 Springer 🌐 English ⚖ 914 KB

Theorems on the time hierarchy for rando

Theorems on the time hierarchy for random access machines

✍ A. G. Ivanov 📂 Article 📅 1982 🏛 Springer US 🌐 English ⚖ 612 KB

The complexity of on-line simulations be

The complexity of on-line simulations between multidimensional turing machines and random access machines

✍ Michael C. Loui; David R. Luginbuhl 📂 Article 📅 1992 🏛 Springer 🌐 English ⚖ 995 KB

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