✦ LIBER ✦

Theorems on the time hierarchy for random access machines

✍ Scribed by A. G. Ivanov

Publisher: Springer US
Year: 1982
Tongue: English
Weight: 612 KB
Volume: 20
Category: Article
ISSN: 1573-8795
DOI: 10.1007/bf01629438

No coin nor oath required. For personal study only.

📜 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

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

On the structure of one-tape nondetermin

On the structure of one-tape nondeterministic turing machine time hierarchy

✍ Kojiro Kobayashi 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 983 KB

With probability one, a random oracle se

With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

✍ Jin-Yi Cai 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 992 KB

The limit theorems for random walk with

The limit theorems for random walk with state space ℝ in a space-time random environment

✍ Wei Gang Wang; Zhen Long Gao; Di He Hu 📂 Article 📅 2008 🏛 Institute of Mathematics, Chinese Academy of Scien 🌐 English ⚖ 197 KB

Limits on the Power of Parallel Random A

Limits on the Power of Parallel Random Access Machines with Weak Forms of Write Conflict Resolution

✍ Faith E. Fich; Russell Impagliazzo; Bruce Kapron; Valerie King; Mirosław Kutyłow 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 403 KB

The ROBUST PRAM is a concurrent-read concurrent-write (CRCW) parallel random access machine in which any value might appear in a memory cell as a result of a write conflict. This paper addresses the question of whether a PRAM with such a weak form of write conflict resolution can compute functions f