Тезис о параллельных вычислениях - Parallel computation thesis

В теория сложности вычислений, то Тезис о параллельных вычислениях это гипотеза в котором говорится, что время используемый (разумной) параллельной машиной полиномиально связан с Космос используется последовательной машиной. Тезис о параллельных вычислениях был сформулирован Чандра и Stockmeyer в 1976 г.^[1]

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

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

Рекомендации