En la memcomputación se cumple NP=P

La solución al problema NP=P debe ser obtenida en el paradigma de la computación con máquinas de Turing. Sin embargo, hay otros paradigmas de computación que no son Turing, como la memcomputación (un tipo de computación analógica neuronal)

[#1 Desactivado]

Existe una demostración matemática de que un memcomputador universal es equivalente a una máquina de Turing no determinista universal.

_{PD: Realmente no he entendido mucho, peor he copiado un párrafo para parecer super interesante.}

[#4 Robus]

Eso ya lo sabemos los que miramos futurama:

media.php?type=comment&id=12947366&version=0&ts=1370242525&image.jpeg

Como puede observarse en el fondo, el libro de los problemas P es igual de gordo que el de los NP.

[#11 ikipol]

Ese tipo de modelos ya existían. Diluyen parte de la complejidad en tiempo en el número de procesadores. Es decir, nada, humo, no es P igual a NP según la definición original de ambas clases.

Con este tipo de titulares gancho no hacen más que confundir al personal

[#12 emulenews]

#10 el tiempo de ejecución del memalgoritmo es polinomial (lineal, de hecho). Lo que sería no polinomial es el tiempo de simularlo en un ordenador convencional.

El problema de la memcomputación es que no es escalable. La razón es que hay que distinguir entre un número exponencial de frecuencias en un intervalo finito del espectro. Obviamente hay límites físicos que impiden escalar el sistema más allá de los "problemas de juguete". Se puede imaginar un sistema que amplifique la diferencia entre las frecuencias cercanas de interés, pero no está demostrado que esta amplificación se pueda realizar con un número polinomial de recursos.

#11 cuidado, no se trata de una computación paralela con un número exponencial de procesadores. El número de procesadores crece linealmente. Lo que crece de forma exponencial es el número de estados (frecuencias en este caso) en cada procesador.


#11 dice "no es P igual a NP según la definición original de ambas clases". Obviamente dicha frase la has copiado del primer párrafo de mi artículo. ¿"titulares gancho"? Sí, lo acepto, está copiado del titular del artículo técnico...

[#2 Desactivado]

NP=P

N=1

¡Resuelto!

[#3 gershwin]

#2 suspenso, N=0 sólo para P=0, para el resto N=1

[#6 Nitros]

#3 ¿Eing?
Si N=1 y P=0:
NP = P
1*0 = 0
0 = 0

No entiendo porque N=0 cuando P=0.

[#8 gershwin]

#7 efectivamente
cc:#6

[#7 sergiobe]

#3 Si P=0 entonces N=indeterminado, porque sería N=0/0.

[#5 Atreides_]

Citando el artículo: "El nuevo memcomputador resuelve este problema en tiempo polinómico con un número polinómico de memprocesadores". O sea, que cuanto más grande sea el problema, más procesadores necesitas.

Tal como lo entiendo (que alguien me corrija si no lo he entendido bien), eso es perfectamente simulable por un ordenador normal, y funcionaría igual de bien si tenemos bastantes procesos ejecutándose en paralelo simultáneamente. Por lo que en esencia, no parece que ganemos mucho.

[#9 emulenews]

#5 se puede simular en un ordenador normal (igual que un ordenador cuántico también se puede simular), pero se pierde la eficiencia del no determinismo y se pierde la "magia" memcomputacional (ya no hay prueba de que NP=P).

[#10 Atreides_]

#9 Claro, entonces el tiempo de ejecución es no polinomial. Pero es que la memcomputación, si lo he entendido bien, requiere que el número de procesadores aumente en orden polinomial respecto al tamaño del problema. Si contamos el tiempo de ejecución de cada uno de esos procesadores de forma individual (eso es lo que significaría simularlo en un ordenador normal), ¿no se volvería a convertir en un problema no polinomial? Por eso digo que en realidad no ganamos nada.