Tesis de computación paralela

En la teoría de la complejidad computacional , la tesis de computación paralela es una hipótesis que establece que el tiempo empleado por una máquina paralela (razonable) está relacionado polinómicamente con el espacio empleado por una máquina secuencial. La tesis de computación paralela fue planteada 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 es decidible bajo el modelo usando no más de pasos para entradas de longitud n es decidible por una máquina no ramificada que usa no más de unidades de almacenamiento para alguna constante k . De manera similar, si una máquina en el modelo no ramificado decide un lenguaje usando no más de almacenamiento, una máquina en el modelo paralelo puede decidir el lenguaje en no más de pasos para alguna constante k . ${\estilo de visualización t(n)}$ $estilo de visualización t(n)^{k}}$ $s(n)$ $Estilo de visualización s(n)^{k}}$

La tesis de la computación paralela 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 potente como para emular la máquina secuencial en tiempo polinomialmente relacionado con el espacio secuencial; compárese máquina de Turing , máquina de Turing no determinista y máquina de Turing alternada . N. Blum (1983) introdujo un modelo para el cual la tesis no se sostiene. ^[2] Sin embargo, el modelo permite hilos paralelos de computación después de pasos. (Véase 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 que es lo suficientemente universal como para emular todos los modelos paralelos "razonables", lo que se adhiere a la tesis. ^[4] Chandra y Stockmeyer originalmente formalizaron y demostraron resultados relacionados con la tesis para máquinas de Turing deterministas y alternadas, que es donde se originó la tesis. ^[5] $2^{2^{O(T(n))}}$ $T(n)$ $2^{O(T(n))}$ $2^{T(n)^{O(1)}}$

Referencias

^ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternancia". FOCS'76: Actas del 17.º Simposio anual sobre fundamentos de la informática . págs. 98-108. doi :10.1109/SFCS.1976.4.
^ Blum, Norbert (1983). "Una nota sobre la 'tesis de la computación paralela'"". Cartas de procesamiento de la 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 la tesis de la computación paralela". ACM SIGACT News . 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 .

[alternation-1] Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternancia". FOCS'76: Actas del 17.º Simposio anual sobre fundamentos de la informática . págs. 98-108. doi :10.1109/SFCS.1976.4.

[2] Blum, Norbert (1983). "Una nota sobre la 'tesis de la computación paralela'"". Cartas de procesamiento de la información . 17 (4): 203–205. doi :10.1016/0020-0190(83)90041-8.

[3] Parberry, I. (1986). "Aceleración paralela de máquinas secuenciales: una defensa de la tesis de la computación paralela". ACM SIGACT News . 18 (1): 54–67. doi : 10.1145/8312.8317 .

[4] 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 .

[5] Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "Alternancia". Revista de la ACM . 28 (1): 114–133. doi : 10.1145/322234.322243 .