La literatura es bastante clara que las RAM de costo unitario con multiplicación primitiva no son razonables, ya que
- no puede ser simulado por máquinas de Turing en tiempo polinómico
- puede resolver problemas completos de PSPACE en tiempo polinómico
Sin embargo, todas las referencias que puedo encontrar sobre este tema (Simon 1974, Schonhage 1979) también involucran operaciones booleanas, división de enteros, etc.
¿Existen resultados para la "razonabilidad" de las RAM que solo tienen suma, multiplicación e igualdad? En otras palabras, ¿cuáles no tienen operaciones booleanas, división entera truncada, resta truncada, etc.?
Uno podría pensar que tales RAM son todavía bastante "irrazonables". La principal señal de alerta es que permiten la generación de enteros exponencialmente grandes en tiempo lineal, y debido a los efectos de multiplicación de convolución, esto puede volverse particularmente complejo. Sin embargo, en realidad no puedo encontrar ningún resultado que muestre que esto permita ningún tipo de resultado "irrazonable" (aceleración exponencial de la máquina Turing, relación irrazonable con PSPACE, etc.).
¿La literatura tiene algún resultado sobre este tema?
fuente
Respuestas:
El otro día estaba leyendo un documento sobre máquinas de acceso aleatorio en paralelo sin operaciones de bits, que se parecía mucho a lo que está describiendo. Para estos modelos, se sabe que NC no es igual a P. Ver aquí: https://epubs.siam.org/doi/10.1137/S0097539794282930
El documento también se puede encontrar en el sitio web del profesor Mulmuley.
fuente