Division is good
- 1 October 1979
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 411-420
- https://doi.org/10.1109/sfcs.1979.13
Abstract
We study the power of RAM acceptors with several instruction sets. We exhibit several instances where the availability of the division operator increases the power of the acceptors. We also show that in certain situations parallelism and stochastic features ('distributed random choices') are provably more powerful than either parallelism or randomness alone. We relate the class of probabilistic Turing machine computations to random access machines with multiplication (but without boolean vector operations). Again, the availability of integer division seems to play a crucial role in these results.Keywords
This publication has 11 references indexed in Scilit:
- The complexity of computing the permanentTheoretical Computer Science, 1979
- Time Bounded Random Access Machines with Parallel ProcessingJournal of the ACM, 1979
- On tape Bounded probabilistic turing machine transducersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- A unified approach to models of synchronous parallel machinesPublished by Association for Computing Machinery (ACM) ,1978
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- AlternationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On parallelism in turing machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- A characterization of the power of vector machinesJournal of Computer and System Sciences, 1976
- On the power of multiplication in random access machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974