Уменьшение сложности с параллелизмом

Возможно ли (вы можете дать пример косую черту) уменьшить вычислительную сложность задачи, используя параллельный алгоритм, который не требует количества процессоров относительно размера ввода?

Если вы имеете в виду O (1) процессоров, то нет, сложность вычислений не может быть уменьшена.

Просто выровняйте работу, проделанную каждым процессором, и сделайте это на одном. Если вы беспокоитесь о синхронизации, то один процессор может легко эмулировать это.

Появляется область грубых параллельных алгоритмов, где время работы (и другое потребление вычислительных ресурсов) рассматривается как функция независимых параметров n (входной размер) и p (количество процессоров), часто при естественном предположении n >> стр .

Хорошей отправной точкой является Google для "синхронного параллелизма".

Вас может заинтересовать эта статья:

Сверхлинейная производительность в параллельных вычислениях в реальном времени Селим Акл.

Он приводит примеры вычислительных задач, в которых «последовательное решение более чем в раз медленнее, чем параллельное решение с n- процессором»; это делается путем творческого толкования концепции «вычислительной проблемы».$n$$n$

$p$$p$

$O(f(n)/p) \rightarrow O((1/p)f(n)) \rightarrow O(cf(n)) \rightarrow O(f(n))$$c=1/p$

$T$$T/p + SomeMoreTime$

Но сложности НЕ меняются.

«Вы не можете вычислить это с 1 процессором, но можете вычислить с 2».

Это невозможно, если предположить, что оба процессора являются ТМ или менее мощной моделью. Из википедии, для многоканальных машин:

Эта модель интуитивно кажется гораздо более мощной, чем модель с одной лентой, но любой многоленточный станок, независимо от размера k, может быть смоделирован на одной ленточной машине, используя только в четыре раза больше времени вычислений (Papadimitriou 1994, Thrm 2.1)

Также для многоголовочных станков, из «Моделирование линейного времени многоголовочных машин Тьюринга с прыжками с головы до головы» Уолтера Дж. Савича и Пола М.Б. Витани:

Основной результат этой статьи показывает, что, учитывая машину Тьюринга с несколькими головками чтения-записи на ленту и имеющую дополнительную операцию сдвига на один ход «сдвигать заданную головку в положение другой заданной головки», можно эффективно построить многоканальная машина Тьюринга с одной головкой чтения-записи на ленту, которая имитирует ее за линейное время; т.е. если исходная машина работает за время T (n), то имитирующая машина будет работать за время cT (n) для некоторой постоянной c.

Возможно, "параллельный или" (учитывая, что две функции возвращают логическое значение, скажите, возвращает ли одна из них значение true, учитывая, что любая из них, но не обе, может не завершиться), может быть то, о чем вы говорите: вы не можете вычислить это с 1 процессором, но может вычислить с 2.

Однако это во многом зависит от того, какую вычислительную модель вы будете использовать, независимо от того, заданы ли вам процессы как черные ящики или как их описание, которое вы можете интерпретировать самостоятельно и т. Д.