En la teoría de la complejidad computacional , la tesis del cálculo paralelo es una hipótesis que establece que el tiempo utilizado por una máquina paralela (razonable) está polinomialmente relacionado con el espacio utilizado por una máquina secuencial. La tesis de la computación paralela fue establecida por Chandra y Stockmeyer en 1976. [1]
En otras palabras, para un modelo computacional que permite que los cálculos se ramifiquen y se ejecuten en paralelo sin límite, un lenguaje formal que se puede decidir bajo el modelo utilizando no más depasos para entradas de longitud n es decidible por una máquina sin ramificación que utiliza no más deunidades de almacenamiento para alguna constante k . De manera similar, si una máquina en el modelo no ramificado decide un idioma usando no más de almacenamiento, una máquina en el modelo paralelo puede decidir el idioma en no más de pasos para alguna constante k .
La tesis del cálculo paralelo no es una declaración formal rigurosa, ya que no define claramente qué constituye un modelo paralelo aceptable. Una máquina paralela debe ser lo suficientemente poderosa para emular la máquina secuencial en el tiempo polinomialmente relacionada con el espacio secuencial; compare la máquina de Turing , la máquina de Turing no determinista y la máquina de Turing alternante . N. Blum (1983) introdujo un modelo para el que la tesis no se sostiene. [2] Sin embargo, el modelo permite hilos paralelos de computación después pasos. (Véase la notación Big O ). Parberry (1986) sugirió que un límite más "razonable" sería o , en defensa de la tesis. [3] Goldschlager (1982) propuso un modelo lo suficientemente universal para emular todos los modelos paralelos "razonables", que se adhiere a la tesis. [4] Chandra y Stockmeyer formalizaron y probaron originalmente los resultados relacionados con la tesis de las máquinas de Turing deterministas y alternas, que es donde se originó la tesis. [5]
Referencias
- ^ Chandra, Ashok K .; Stockmeyer, Larry J. (1976). "Alternancia". FOCS'76: Actas del 17º Simposio Anual sobre Fundamentos de la Ciencia de la Computación . págs. 98-108. doi : 10.1109 / SFCS.1976.4 .
- ^ Blum, Norbert (1983). "Una nota sobre la 'tesis de computación paralela ' ". Cartas de procesamiento de información . 17 (4): 203-205. doi : 10.1016 / 0020-0190 (83) 90041-8 .
- ^ Parberry, I. (1986). "Aceleración paralela de máquinas secuenciales: una defensa de tesis de computación paralela". Noticias ACM SIGACT . 18 (1): 54–67. doi : 10.1145 / 8312.8317 .
- ^ Goldschlager, Leslie M. (1982). "Un patrón de interconexión universal para computadoras paralelas". Revista de la ACM . 29 (3): 1073–1086. doi : 10.1145 / 322344.322353 .
- ^ Chandra, Ashok K .; Kozen, Dexter C .; Stockmeyer, Larry J. (1981). "Alternancia". Revista de la ACM . 28 (1): 114-133. doi : 10.1145 / 322234.322243 .