Size Matters: Logarithmic Space is Real Time

Autor:	Selim G. Akl, Stefan D. Bruda
Rok vydání:	2007
Předmět:	Optimization problem Logarithm Computer science Computation Parallel algorithm Computer Graphics and Computer-Aided Design Computer Science Applications Nondeterministic algorithm NL-complete Hardware and Architecture Bounded function Constant (mathematics) Algorithm Software
Zdroj:	International Journal of Computers and Applications. 29:327-336
ISSN:	1925-7074 1206-212X
DOI:	10.1080/1206212x.2007.11441863
Popis:	We show that all the problems solvable by a nondeterministic machine with logarithmic work space (NL) can be solved in real time by a parallel machine, no matter how tight the real-time constraints are. We also show that several other real-time problems are in effect solvable in nondeterministic logarithmic space once their real-time constraints are dropped and they become non-real-time. We thus conjecture that NL contains exactly all the problems that admit feasible real-time parallel algorithms. The issue of real-time optimization problems is also investigated. We identify the class of such problems that are solvable in real time. In the process, we determine the computational power of directed reconfigurable multiple bus machines (DRMBMs) with polynomially bounded resources and running in constant time, which is found to be the same as the power of directed reconfigurable networks with the same properties. We also show that write conflict resolution rules such as Priority or even Combining do not add computational power over the Collision rule, and that a bus of width 1 (a wire) suffices for any constant time computation on DRMBM.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::413dabfa2baa7c5f0e10b363acd79f14 https://doi.org/10.1080/1206212x.2007.11441863 Zobrazit plný text záznamu