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)$ 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}$ 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)$ armazenamento, uma máquina no modelo paralelo pode decidir a linguagem em não mais do que $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))}}$ processos de computação paralela após $T(n)$ passos. (Veja notação Grande-O.) Em 1986, Parberry^[3] sugeriu uma forma mais "razoável" que seria $2^{O(T(n))}$ ou $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.