Tese da computação paralela

Na teoria da complexidade computacional, a tese da computação paralela é uma hipótese que afirma que o tempo é utilizado por uma máquina paralela (razoável) e é polinomialmente relacionada com o espaço utilizado por uma máquina seqüencial. A tese de computação paralela foi estabelecido por Chandra e Larry Stockmeyer em 1976[1] (ver Referências).

Em outras palavras, é um modelo computacional que permite cálculos em ramificação e executados em paralelo sem limites, uma linguagem formal que é decidível sob o modelo usando não mais que t ( n ) {\displaystyle t(n)} passos para as entradas de comprimento n é decidível por uma máquina no modelo desramificação usando não mais que t ( n ) k {\displaystyle t(n)^{k}} unidade de armazenamento para alguma constante k. Da mesma forma, se uma máquina no modelo de desramificação decide uma linguagem utilizando não mais do que s ( n ) {\displaystyle s(n)} armazenamento, uma máquina no modelo paralelo pode decidir a linguagem em não mais do que s ( n ) k {\displaystyle s(n)^{k}} passos para alguma constante k.

A tese de computação paralela não é uma declaração formal rigorosa, uma vez que não define claramente o que constitui um modelo aceitável paralelo. A máquina paralela deve ser suficientemente poderosa para emular a máquina seqüencial em tempo polinomial relacionadas com o espaço seqüencial; compare máquina de Turing, máquina de Turing não-determinística, e máquina de Turing alternada. Em 1983, N. Blum[2] introduziu um modelo em que a tese não se sustenta. No entanto, o modelo permite 2 2 O ( T ( n ) ) {\displaystyle 2^{2^{O(T(n))}}} processos de computação paralela após T ( n ) {\displaystyle T(n)} passos. (Veja notação Grande-O.) Em 1986, Parberry[3] sugeriu uma forma mais "razoável" que seria 2 O ( T ( n ) ) {\displaystyle 2^{O(T(n))}} ou 2 T ( n ) O ( 1 ) {\displaystyle 2^{T(n)^{O(1)}}} , em defesa da tese. Em 1982, Goldschlager[4] propôs um modelo que é suficientemente universal para emular todas os modelos paralelos "razoáveis", que aderem à tese. Chandra e Stockmeyer originalmente formalizaram e provaram resultados relacionadas com a tese para máquinas Turing determinísticas e alternadas, que é de onde se originou a tese.

Referências

  1. * Chandra, A.K. and Stockmeyer, L.J., 'Alternation,' Journal of the ACM, Volume 28, Issue 1, pp. 114-133, 1981.
  2. * Blum, N., "A note on the 'parallel computation thesis'," Inf. Proc. Lett., volume 17, pp. 203-205, 1983.
  3. * Parberry, I., 'Parallel speedup of sequential machines: a defense of parallel computation thesis,' ACM SIGACT News, Volume 18, Issue 1, pp. 54-67, 1986.
  4. * Goldschlager, Leslie M., 'A Universal Interconnection Pattern for Parallel Computers,' Journal of the ACM, Volume 29, Issue 3, pp. 1073-1086, 1982.