Análogo exponencial de NC?

La clase de Nick (NC) es la clase de problemas que se pueden decidir en el tiempo de poli-log utilizando un número polinómico de procesadores.

Quiero saber sobre el análogo exponencial, que cubriría los problemas que se pueden decidir en el tiempo polinómico usando un número exponencial de procesadores.

Lo que estoy buscando es un nombre para esta clase y cualquier relación conocida entre esta clase y otras clases de complejidad, o cualquier problema canónico para la clase. Parece sencillo que contendría NP y co-NP, y creo que está contenido en PSPACE, pero no estoy seguro de mucho más al respecto.

El tiempo en los circuitos corresponde a la profundidad. Por lo tanto, por tiempo polinómico significa profundidad polinómica.

El número de procesadores es el tamaño del circuito, es decir, el número de puertas en el circuito. Entonces, por número exponencial de procesadores, permite un tamaño exponencial. Esta seria la clase$\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$. Pero cada función ya está en$\mathsf{DepthSize}(2, 2^{n^{O(1)}})$ (piense en el CNF de la función que desea calcular).

La conclusión es que el número exponencial de procesadores es demasiado fuerte para ser útil por sí solo.

Una restricción razonable para poner es limitar la cantidad de comunicación entre diferentes procesos. Por ejemplo, cada proceso solo puede comunicarse polinómicamente con muchos otros procesos y los mensajes tienen un tamaño polinómico. Eso sería$\mathsf{PSpace}$como se explica en las respuestas a la pregunta de Aterm sobre teoría . Otra forma de verlo para recordar que $\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$, problemas computables alternando máquinas de Turing en tiempo polinómico. La alternancia en las máquinas de Turing consiste esencialmente en bifurcar nuevos procesos y luego unirse después de que terminen tomando la conjunción / disyunción de sus valores de retorno.