Reduzindo a complexidade com paralelismo

É possível (barra você pode fornecer um exemplo) reduzir a complexidade computacional de um problema usando um algoritmo paralelo que não requer um número de processadores em relação ao tamanho da entrada?

Se você quer dizer processadores O (1), então não, a complexidade da computação não pode ser reduzida.

Basta alinhar o trabalho realizado por cada processador e fazê-lo em um único. Se você está preocupado com a sincronização, um processador pode facilmente emular isso.

Existe um campo emergente de algoritmos paralelos de granulação grossa, em que o tempo de execução (e outro consumo de recursos computacionais) é considerado uma função dos parâmetros independentes n (tamanho da entrada) ep (número de processadores), geralmente sob uma suposição natural n >> p .

Um bom ponto de partida é procurar no Google por "paralelismo síncrono em massa".

Você pode estar interessado neste artigo:

Desempenho Superlinear em Computação Paralela em Tempo Real por Selim Akl.

$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$

Mas nenhuma mudança de complexidade.

"você não pode computar com 1 processador, mas com 2."

Isso não é possível, supondo que os dois processadores sejam TMs ou um modelo menos poderoso. Da wikipedia, para máquinas com várias fitas:

Esse modelo parece intuitivamente muito mais poderoso que o modelo de fita única, mas qualquer máquina de fita múltipla, independentemente do tamanho k, pode ser simulada por uma máquina de fita única usando apenas quatro vezes mais tempo de computação (Papadimitriou 1994, Thrm 2.1)

Também para máquinas com cabeçote múltiplo, de "Simulação linear no tempo de máquinas de cabeçote com cabeçote múltiplo com saltos cabeçote a cabeçote" de Walter J. Savitch e Paul MB Vitányi:

O principal resultado deste artigo mostra que, dada uma máquina de Turing com várias cabeças de leitura / gravação por fita e que possui a operação adicional de troca de turno "desloca uma cabeça para a posição de outra cabeça", pode-se efetivamente construir uma Máquina de Turing multitape com uma única cabeça de leitura / gravação por fita que simula em tempo linear; isto é, se a máquina original operar no tempo T (n), a máquina de simulação operará no tempo cT (n), por alguma constante c.

Talvez "paralelo ou" (dadas duas funções retornando um booleano, diga se uma delas retorna verdadeira, já que alguma delas, mas não as duas, pode falhar em terminar) pode ser o que você está falando: você não pode calcular com 1 processador, mas pode calcular com 2.

No entanto, isso depende muito de qual modelo computacional você usará, se você recebe os processos como caixas pretas ou como a descrição deles que você pode interpretar, etc.