Simulación en tiempo constante de un modelo R-Mesh en un LR-Mesh
| Autor: | Córdova Flores, Carlos Alberto |
|---|---|
| Přispěvatelé: | JOSE ALBERTO FERNANDEZ ZEPEDA |
| Jazyk: | Spanish; Castilian |
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Centro de Investigación Científica y de Educación Superior de Ensenada CICESE Repositorio Institucional CICESE |
| Popis: | Se creía que el modelo LR-Mesh era computacionalmente menos poderoso que el modelo R-Mesh. Omer Reingold mostró un algoritmo para la máquina de Turing que resuelve USTCON requiriendo O(logN) unidades de espacio, implicando que las clases de complejidad L y SL son equivalentes. Los modelos LR-Mesh y R-Mesh son capaces de resolver los problemas de las clases L y SL en tiempo constante, respectivamente. Por lo tanto, los resultados de Reingold implican que los modelos LR-Mesh y R-Mesh son computacionalmente igual de poderosos. En el presente trabajo se describe una simulación del modelo R-Mesh en el LR-Mesh en tiempo constante. La mejor simulación conocida requería de O(logN) unidades de tiempo. Se muestra cómo se puede convertir un grafo regular cualquiera en un expansor y como resolver el problema USTCON en un expansor en el modelo LR-Mesh siguiendo el algoritmo de Reingold. Con estos resultados se construye la smulación entre los modelos en tiempo constante. Finalmente se muestra un análisis de los recursos (procesadores) requeridos por dicha simulación. There was the assumption that the LR-Mesh model was computationally less powerful than the R-Mesh. Omer Reingold showed an algorithm for the Turing machine that solves USTCON problem with O(logN) space units, implying that the complexity classes L and SL are equivalent. The LR-Mesh and R-Mesh models are capable of solving the problems that belong to the classes L and SL in constant time, respectively. Hence, Omer Reingold’s results implies that the model LR-Mesh is computationally as powerful as the R-Mesh. The present work decribes a simulation of the R-Mesh model on the LR-Mesh in constant time. The best simulation known required O(logN) time units. It shows how to transform a regular graph into an expander and how to solve USTCON in an expander graph on the LR-Mesh, following Reingold’s algorithm. With these results the constant time simulation between the models is constructed. Finally it shows an analysis of the resources (processors) required for the stated simulation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|