Reducción de la complejidad con paralelismo

¿Es posible (barra oblicua puede proporcionar un ejemplo) para reducir la complejidad computacional de un problema mediante el uso de un algoritmo paralelo que no requiere una serie de procesadores en relación con el tamaño de entrada?

Si te refieres a los procesadores O (1), entonces no, la complejidad del cálculo no se puede reducir.

Simplemente alinee el trabajo realizado por cada procesador y hágalo en uno solo. Si le preocupa la sincronización, entonces un procesador puede emularlo fácilmente.

Hay un campo emergente de algoritmos paralelos de grano grueso, donde el tiempo de ejecución (y otros consumos de recursos computacionales) se considera como una función de parámetros independientes n (tamaño de entrada) yp (número de procesadores), a menudo bajo un supuesto natural n >> p .

Un buen punto de partida es buscar en Google "paralelismo masivo sincrónico".

Quizás te interese este artículo:

Rendimiento superlineal en computación paralela en tiempo real por Selim Akl.

Proporciona ejemplos de problemas computacionales en los que "la solución secuencial es más de veces más lenta que una solución paralela n- procesador"; Esto se hace interpretando creativamente el concepto de un "problema computacional".$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$

Pero NO hay cambio de complejidad.

"No se puede calcular con 1 procesador, pero se puede calcular con 2".

Esto no es posible, suponiendo que ambos procesadores sean TM o un modelo menos potente. De wikipedia, para máquinas de cintas múltiples:

Este modelo intuitivamente parece mucho más poderoso que el modelo de una sola cinta, pero cualquier máquina de cintas múltiples, sin importar cuán grande sea la k, puede ser simulada por una máquina de una sola cinta usando solo cuadráticamente más tiempo de cálculo (Papadimitriou 1994, Thrm 2.1)

También para máquinas de múltiples cabezales, desde "Simulación de tiempo lineal de máquinas de turing de múltiples cabezas con saltos cabeza a cabeza" por Walter J. Savitch y Paul MB Vitányi:

El resultado principal de este documento muestra que, dada una máquina Turing con varios cabezales de lectura-escritura por cinta y que tiene la operación de cambio de un movimiento adicional "cambiar un cabezal dado a la posición de otro cabezal dado", se puede construir efectivamente un Máquina de Turing multitapa con un solo cabezal de lectura-escritura por cinta que lo simula en tiempo lineal; es decir, si la máquina original funciona en el tiempo T (n), entonces la máquina de simulación funcionará en el tiempo cT (n), para alguna constante c.

Quizás "paralelo o" (dadas dos funciones que devuelven un valor booleano, diga si una de ellas devuelve verdadero, dado que cualquiera de ellas, pero no ambas, podría no terminar) podría ser de lo que está hablando: no puede calcular con 1 procesador, pero puede calcular con 2.

Sin embargo, esto depende mucho del modelo computacional que utilizará, ya sea que le den los procesos como cuadros negros o como su descripción, que puede interpretar usted mismo, etc.