Диссертация по параллельным вычислениям

В теории сложности вычислений тезис о параллельных вычислениях — это гипотеза , которая утверждает, что время, используемое (разумной) параллельной машиной, полиномиально связано с пространством, используемым последовательной машиной. Тезис о параллельных вычислениях был выдвинут Чандрой и Стокмейером в 1976 году.

Другими словами, для вычислительной модели , которая позволяет вычислениям разветвляться и выполняться параллельно без ограничений, формальный язык , который разрешим в рамках модели, используя не более $t(n)$ шагов для входных данных длины n разрешима неветвящейся машиной, используя не более $t(n)^{k}$ единицы хранения для некоторой константы k . Аналогично, если машина в неветвящейся модели определяет язык, используя не более $s(n)$ В памяти машина в параллельной модели может определить язык не более чем за $s(n)^{k}$ шаги для некоторой константы k .

Тезис о параллельных вычислениях не является строгим формальным утверждением, поскольку он четко не определяет, что представляет собой приемлемая параллельная модель. Параллельная машина должна быть достаточно мощной, чтобы имитировать последовательную машину во времени, полиномиально связанном с последовательным пространством; сравните машину Тьюринга , недетерминированную машину Тьюринга и альтернативную машину Тьюринга . Н. Блюм (1983) предложил модель, для которой этот тезис не справедлив. Однако модель позволяет $2^{2^{O(T(n))}}$ параллельные потоки вычислений после $T(n)$ шаги. (См. обозначение Big O. ) Парберри (1986) предположил, что более «разумной» границей будет $2^{O(T(n))}$ или $2^{T(n)^{O(1)}}$, в защиту диссертации. Гольдшлагер (1982) предложил модель, которая достаточно универсальна, чтобы имитировать все «разумные» параллельные модели, соответствующие этому тезису. Чандра и Стокмейер первоначально формализовали и доказали результаты, связанные с тезисом о детерминированных и знакопеременных машинах Тьюринга, откуда и возникла эта диссертация.