¿Cuál fue la primera novela ambientada en universos donde P=NP?

Me pregunto si alguien ha escrito una novela ambientada en un universo donde P=NP, en el caso de que haya más de una, ¿cuál fue la primera?

ingrese la descripción de la imagen aquí

En este universo todos los problemas que pudieran ser verificados en tiempo polinomial (NP) (dada la solución) también podrían ser resueltos en tiempo polinomial (P).

por una buena razón, me imagino. Puedo ver el diálogo ahora mismo.
Greg Egan escribió enteros oscuros y luminosos, que tratan sobre la calculabilidad y la complejidad en una configuración de álgebra pura. Si eso puede funcionar, también puede funcionar una novela sobre P=NP :)
La página de inicio de MathFiction sería un buen punto de partida para algo como esto.
No es una novela, pero Russell Impagliazzo (un destacado investigador de la teoría de la complejidad) escribió un breve artículo que describe cinco mundos en los que suceden tales cosas (el universo de Algorithmica tiene P = NP, Cryptomania tiene criptografía de clave pública garantizada, etc.). Solo pensé en mencionarlo en caso de que tenga curiosidad por un punto de vista más teórico sobre cómo sería un mundo con P = NP. blog.computationalcomplexity.org/2004/06/…
Dr. G +1, pero no estoy seguro de qué versiones de los cuentos de Egan ha leído: P, pero lo tomé como que los valores de verdad de las declaraciones aritméticas se comportaban como el giro de una partícula cuántica, y el cálculo de matemática Los resultados fueron cambiar estos valores de verdad, en detrimento de un 'otro universo paralelo'. La física en sí se vio afectada por el cambio de las reglas de las matemáticas, por lo que hubo un caos total cuando los 'otros' se defendieron. (Y sí, tengo un doctorado en matemáticas puras)
... y ¿cómo sabes que P=NP no es cierto nuestro universo? Házmelo saber y compartiré el millón de dólares contigo.
@DavidRoberts Debería haber formulado la pregunta como una novela ambientada en un universo donde sabemos P = NP :) Re: Egan, interpreté la historia como un giro en la definición intencional. Nuestra teoría se basa en la definición intensional, no significa que el universo esté de acuerdo, y dado que no hemos tratado de verificar la versión extensional de nuestras definiciones, el universo físico podría estar en desacuerdo.
Tal vez todos ellos... Ya que es un problema sin resolver en este momento. :-)
¿Puedes explicar, en términos realmente simples, qué significa P=NP y cómo sabríamos si un libro que estamos leyendo estaría en ese universo?
@Wikis: En un universo P = NP, encontrar una solución correcta para una jerarquía de problemas grande y bien definida sería tan complejo como reconocer que la solución propuesta para tal problema es correcta. Por ejemplo, en nuestro universo reconocer que una obra de arte es grandiosa parece ser mucho más fácil que crear una gran obra. En un universo donde P = NP, la cantidad de esfuerzo requerido sería la misma o solo ligeramente mayor cuando se mira en términos del tamaño del problema a resolver. El descifrado fácil de casi todas las formas de encriptación es otra señal de un universo P=NP.
@DrG: Greg Egan probablemente podría escribir una novela donde P y NP sean los protagonistas. Ese tipo hace que Kim Stanley Robinson parezca George Lucas.

Respuestas (10)

Star Trek, Varios, 1966 (primera aparición)

P = NP en el universo de Star Trek, pero la gente no lo sabe. Evidencia:

  1. Hay encriptación, pero siempre se puede romper. P = NP le permitirá descifrar todo menos las libretas de un solo uso, pero la Federación continúa obstinadamente usando cifrados basados ​​​​en NP.

  2. La eficacia del traductor universal. P=NP haría que aprender nuevos idiomas fuera pan comido, al menos para una computadora. Los sistemas de aprendizaje serían tan simples y directos de implementar que no quedaría ni un lingüista con trabajo.

  3. La eficacia del biofiltro. El transportador filtra de forma rutinaria organismos desconocidos, virus y otros peligros cuando los tripulantes son transportados a bordo del barco. Pero "biofiltro" es un término engañoso, ya que recuerda una especie de tamiz que atrapa todas las cosas malas y deja pasar solo las buenas. En realidad, ejecutar un "filtro" de este tipo sobre los datos de transporte sería la madre de todos los problemas de isomorfismo de subgrafo inducido , ya que tendría que identificar todas las estructuras del tamaño de un virus en un organismo repleto de tales estructuras. P=NP elimina mágicamente el exponente relacionado con la entrada que hace que tales problemas sean intratables incluso para gráficos pequeños.

  4. La inteligencia artificial autoconsciente se crea con facilidad. Wesley Crusher creó uno por accidente. Lo mismo hizo Richard Daystrom. La computadora Enterprise D cocinó a Moriarty en sus ciclos de repuesto, el Dr. Farallon creó los Exocomps, y así sucesivamente. Todo lo que parece que necesita hacer es construir algo equivalente a un sistema de prueba de teoremas y dejar que se ejecute el tiempo suficiente para tropezar con la prueba de que P o alguna otra clase tratable es equivalente a NP y el sistema está en marcha.

O tal vez los habitantes de Star Trek están colapsando la jerarquía polinomial por medios tecnológicos. La Federación, Borg, etc. parecen tener fácil acceso a máquinas del tiempo, agujeros de gusano, materia exótica y señalización superlumínica, por lo que podrían estar usando curvas cerradas similares al tiempo para el cálculo. Esto , según Scott Aaronson , les permitiría resolver eficientemente problemas completos de PSPACE.

+1 por usar evidencia del mundo para mostrar algo. El mas excelente.
Creo que simplemente abordan los tres puntos que emites mediante la potencia informática bruta. Un DTM puede resolver exactamente los mismos problemas que un NTM, pero lleva más tiempo. Entonces, si sus habilidades de ingeniería son lo suficientemente locas, pueden producir computadoras realmente rápidas (paralelas) (también probablemente encontraron un par de buenas heurísticas para algunos problemas NP-difíciles en el camino). Entonces, no estoy seguro de cómo se aplican sus argumentos.
@Blue Tal vez debería haber escrito P = NP le permite descifrar todo lo útil , excepto las almohadillas de un solo uso. Si no puede verificar el descifrado en tiempo polinomial, que es lo que significa tener un criptosistema fuera de NP, incluso con la clave de descifrado no es computacionalmente factible. Eso para mí no es un criptosistema útil.
@bitmask: está en algún lugar de los manuales técnicos que Star Trek ejecuta el núcleo de la computadora dentro de un campo warp modificado donde el tiempo corre a un ritmo diferente.
@MichaelEdenfield: Si existen técnicas de resolución de problemas estrictamente más poderosas que un DTM muy rápido, y para aplicaciones prácticas, P y NP han perdido relevancia, eso en sí mismo es una evidencia muy sólida de P = NP en el universo. En un universo P!=NP, el descubrimiento de tales técnicas es muy poco probable.
@Tynam P y NP se definen estrictamente en términos de lo que es posible hacer con máquinas Turnig deterministas y no deterministas; simplemente no tiene sentido hablar de ellos fuera de ese contexto. Ya hay evidencia de que las computadoras cuánticas podrían proporcionar una forma de realizar cálculos no deterministas, por ejemplo...
@MichaelEdenfield: Buen punto; No había pensado en el ángulo de la computadora cuántica / NDTM. Dicho esto, la diferencia práctica entre un universo P=NP y un universo de cómputo ND significativamente más poderoso parece ser pequeña. (Pero entonces, no estoy convencido de que el cerebro humano sea significativamente más poderoso que un DTM; el paralelismo no es lo mismo que la complejidad algorítmica).
¿Podrías ponerle una fecha a esto?
@AncientSwordRage Fecha de qué?
@Kyle, la fecha en la que crees que la serie Star Trek se presentó por primera vez como P = NP.
@AncientSwordRage Al elegir entre mis ejemplos, creo que debería ser el primer episodio que presente el uso del traductor universal en una situación de primer contacto. En TOS, ese sería el episodio 10 de la primera temporada, "La maniobra de Corbomite", cuando Enterprise se encontró con Baalok y la pelota divertida de la Primera Federación.
@kyle eso lo convierte en 1966, que es un contendiente. ¿Te opondrías a que lo edite en tu respuesta?
@AncientSwordRage no, adelante.

Anticuerpos, Charles Stross, 2000

Una breve historia que gira en torno al hecho de que resolver P=NP es un requisito previo necesario para desarrollar una inteligencia informática. Está disponible en su libro Brindis . Stross ha puesto el texto completo de este libro en línea. ( Este enlace lo llevará directamente a la historia).

Y según el sitio de Stross, la historia fue:

Publicado en Interzone #157; republicado en "La mejor ciencia ficción del año # 18" (ed. Gardner Dozois). Mencionado en la "Lista de lecturas recomendadas" de Locus en 2000. Preseleccionado para el premio Theodore Sturgeon de 2001 (perdió ante "Tendoleo's Story" de Ian MacDonald).

El otro libro de Stross que trata sobre esto es The Atrocity Archives , donde Alan Turing resolvió P=NP, pero luego descubrieron que hacerlo permitía el acceso a los Reinos Cthonic, por lo que ahora existe una rama entera del Gobierno para evitar que este descubrimiento se haga público. .

En la serie "Zones of Thought" de Vernor Vinges ("The Blabber", A Fire Upon the Deep , A Deepness in the Sky y el próximo The Children of the Sky ), el cálculo es más fácil en algunas partes de la galaxia, lo que permite cosas como inteligencia artificial y viajes FTL.

Se ha especulado (pero no hay evidencia directa en los libros) que P=NPen estas zonas.

¿Hay alguna evidencia indirecta? Mi recuerdo es que el cálculo es diferente fuera de la Zona lenta (la tesis de Church solo se mantiene en la Zona lenta) y algo como P = NP no necesita aplicarse o incluso tener sentido allí.
En A Fire Upon the Deep , los Skode Riders encuentran que la creencia de Pham en el cifrado de clave pública es graciosa. De eso podemos concluir que P == NPen el Más Allá.
No necesariamente: las computadoras cuánticas teóricamente podrían manejar problemas NP-completos en tiempo polinomial, incluso sin P=NP.
No, ellos no pueden. Las operaciones en las que los algoritmos de cifrado de clave pública más extendidos se basan en ser difíciles (factorización, registro discreto) no son (se cree que son) NP-completas. Estos son los problemas que las computadoras cuánticas teóricamente pueden resolver en tiempo polinomial. Dicho esto, existen algoritmos de cifrado de clave pública que se basan en problemas NP-completos, pero estos no son de uso generalizado (todavía...)
@BlueRaja Actualmente no conocemos ninguna forma de usar una computadora cuántica para resolver problemas completos de NP de manera eficiente, pero está afirmando que eso P < NP <= BQPes falso y no conozco ninguna prueba para esto. Estoy de acuerdo en que probablemente sea falso, pero lo declaras como un hecho.
@Code: Sí, lo siento, no hablé con cuidado. Quise decir que no se sabe (o se cree) que sea teóricamente posible.
Iba a decir Zonas de Pensamiento. No estoy seguro de que sea literalmente cierto que P = NP, en el sentido de que es posible que en cualquier ubicación particular de una zona , nuestra intuición de que puede construir un problema NP que no puede resolver fácilmente es cierta. Pero creo que es lo suficientemente similar como para que valga la pena mencionarlo, ya que puedes moverte (o enviar un mensaje) a una zona más alta, donde tu problema se resolverá fácilmente.

En el fanfic Harry Potter y los métodos de la racionalidad de Eliezer S. Yudkowsky, Harry obtiene una máquina del tiempo e intenta factorizar el producto de dos grandes números primos usando esta máquina, con un resultado un tanto extraño. Entonces no está completamente dado eso NP=P, pero parece probable.

Eso no tiene sentido. Un problema pertenece a P, si existe una cierta máquina de Turing que resuelve este problema (la definición de NP es similar). No importa si existen otros medios concebibles para resolver este problema. Al piratear los bucles de tiempo, Harry superó la pregunta P = NP.
Sí, si su prueba fue exitosa, habría significado que existe un dispositivo de computación 'más fuerte' que la máquina de Turing y, por lo tanto, refutó la tesis de Church. Entonces, si deja NP definido usando máquinas de Turing, no probaría 'NP = P'.
IIRC, se ha demostrado que P = PSPACE (que es más fuerte que P = NP) para una máquina de Turing equipada con la capacidad de enviar datos hacia atrás en el tiempo, incluso si está sujeto a la autoconsistencia de Novikov. Todavía es posible que P = PSPACE para las máquinas de Turing ordinarias, pero los teóricos de la complejidad de la "corriente principal" lo consideran incluso menos plausible que P = NP.

The Roaring Trumpet de Spague de Camp y Fletcher Pratt, publicado en mayo de 1940 en Unknown. Aquí, los psicólogos postulan que los esquizofrénicos en realidad acceden mentalmente a universos alternativos y, al aplicar las ecuaciones adecuadas, uno podría viajar a ese universo alternativo y traer la mente de la persona de vuelta a nuestro universo. Fue un ejercicio intelectual que el protagonista principal, Harold Shea, decide poner a prueba. Se refiere en broma al viaje a través del silogismóvil, pero implica estudiar y construir la lógica del destino del universo y recitarlo en voz alta. Esto generalmente comienza con "si P es igual a no P..." y continúa desde allí. Toda la serie Enchanter los hace saltar del universo a través de la mitología y los cuentos de hadas y las obras clásicas al hacerlo.

Sospecho, sin haberlo pensado nunca, que al comenzar con P=NP, estaban distinguiendo el universo como uno en el que funciona la magia.

Sin embargo, "NP" en "P = NP" no significa "no P". La redacción podría estar basada en un malentendido, pero estoy seguro de que el problema P vs. NP no se formuló en 1940, por lo que probablemente solo pretendían afirmar una contradicción ("P" es una proposición genérica; al asumir P y no P , cualquier cosa puede seguir.) AFAIK, la pregunta P vs NP se planteó por primera vez como tal en 1971.

Némesis, Isaac Asimov, 1989

Habla de imposibilidades y las implicaciones de un universo donde las leyes de la física no se aplican.

Proporcione una fecha con su respuesta, la próxima vez y explique por qué esto se relaciona explícitamente con P = NP.

El efecto de la práctica , David Brin, 1984

Este parece un candidato probable. En el universo representado, una sonda robótica de nuestro universo comienza a optimizarse tanto física como mentalmente mientras la inteligencia humana permanece inalterada. También los objetos físicos tienden a optimizarse a sí mismos: un trineo de madera desarrolla lubricante para deslizarse fácilmente por la carretera. Este efecto de práctica puede ser potenciado por un estado especial de trance donde la solución aparece inmediatamente por sí misma, por lo tanto, los objetos inanimados realizan una evolución de amplio rango dentro de un tiempo no polinomial (buscando una variedad casi infinita de posibles soluciones dentro de un corto período de tiempo) . Este universo realmente trasciende P=NP.

Edite por qué cree que este es el caso.

En la historia Starshield Sentinels de Margaret Weis y Tracy Hickman, había computadoras/inteligencias artificiales que podían responder cualquier pregunta instantáneamente al enviar la pregunta atrás en el tiempo, dándole 'tiempo' para resolverla. El único inconveniente de esto fue que la computadora tuvo que estar 'despierta' el tiempo suficiente para resolverlo (algo así como Deep Thought de The Hitchhiker's Guide to the Galaxy que necesita 10 millones de años para resolver la cuestión de la vida, el universo y todo).

Si bien no sé si esto se aplica exactamente a todo P = NP, resuelve la cláusula variable/resolver en la pregunta.

Por supuesto, todas las computadoras se vuelven locas e intentan matar a todos en la historia. ¿No podemos dejar de intentar inventar robots asesinos ahora?

Si no me equivoco, en ' The Ragged Astronauts ' de Bob Shaw, uno de los personajes dedica un rato a explicar cómo pi es 3 a otro. Si pi es 3, solo puedo imaginar cómo es el resto de la física. (Solo recuerdo la escena porque toda la escena estaba un poco fuera de lugar, lo cual era bastante inusual para el libro; por lo demás, era una historia genial).

¿Cómo se relaciona esto con p=np?
¿Cuál fue la primera novela ambientada en universos donde P=NP?
RespuestasAquíPolítica de privacidad1y, 1v