Paralelismo en máquinas de acceso aleatorio

Se presenta un modelo de computación basado en máquinas de acceso aleatorio que operan en paralelo y comparten una memoria común. El poder computacional de este modelo está relacionado con el de los modelos tradicionales. En particular, las RAM paralelas deterministas pueden aceptar en tiempo polinómico exactamente los conjuntos aceptados por las máquinas de Turing de cinta polinómica acotada; las RAM no deterministas pueden aceptar en tiempo polinómico exactamente los conjuntos aceptados por las máquinas de Turing de tiempo exponencial no determinista acotadas. Resultados similares se aplican a otras clases. También se considera el efecto de limitar el tamaño de la memoria común.