Pregunta:
¿Cuál fue la primera novela ambientada en universos donde P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

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

enter image description here

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

por una buena razón, me imagino. Puedo ver el diálogo ahora mismo.
Greg Egan escribió Dark integers y Luminous, 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 :)
No es una novela, pero Russell Impagliazzo (un investigador de la teoría de la complejidad superior) escribió un artículo corto que describe cinco mundos en los que suceden tales cosas (el universo Algorithmica tiene P = NP, Cryptomania ha garantizado la criptografía de clave pública, etc.). Solo pensé en mencionarlo en caso de que sienta curiosidad por un punto de vista más teórico sobre cómo se vería un mundo con P = NP. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
Dr. G +1, pero no estoy seguro de qué versiones de los cuentos de Egan ha leído: P, pero supuse 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 Los resultados estaban cambiando estos valores de verdad, en detrimento de un "otro universo paralelo". La física misma se vio afectada por el cambio de las reglas de las matemáticas, por lo que hubo un caos generalizado cuando los "otros" se defendieron. (Y sí, tengo un doctorado en matemáticas puras)
... y ¿cómo sabes que P = NP no es cierto en nuestro universo? Avísame 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 que P = NP :) Re: Egan, interpreté la historia como un giro en la definición intensional. Nuestra teoría se basa en una definición intensional, no significa que el universo esté de acuerdo, y dado que no hemos intentado verificar la versión extensional de nuestras definiciones, el universo físico podría no estar de acuerdo.
Quizás todos ... Ya que es un problema sin resolver en este momento. :-)
La [página de inicio de MathFiction] (http://kasmana.people.cofc.edu/MATHFICT/) sería un buen punto de partida para algo como esto.
¿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 a una jerarquía de problemas grande y bien definida sería tan complejo como _reconocer_ que la solución propuesta a tal problema es correcta. Por ejemplo, en nuestro universo, reconocer que una obra de arte es excelente 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 modestamente mayor cuando se mira en términos del tamaño del problema a resolver. El descifrado fácil de casi todas las formas de cifrado es otro signo de un universo P = NP.
@DrG: Greg Egan probablemente podría escribir una novela en la que P y NP sean los protagonistas. Ese tipo hace que Kim Stanley Robinson se parezca a George Lucas.
Diez respuestas:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

Star Trek, Various, 1966 (ocurrencia más temprana)

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

  1. Hay cifrado, pero siempre se puede romper. P = NP le permitirá descifrar todo, excepto los blocs de notas de una sola vez, pero la Federación continúa obstinadamente utilizando cifrados basados ​​en NP.

  2. La eficacia del traductor universal. P = NP haría que aprender nuevos idiomas fuera muy fácil, al menos para una computadora. Los sistemas de aprendizaje serían tan simples y sencillos de implementar que no quedaría ningún lingüista con un trabajo.

  3. La eficacia del biofiltro. El transportador filtra de forma rutinaria organismos desconocidos, virus y otros peligros cuando los tripulantes viajan a bordo del barco. Pero "biofiltro" es un término engañoso, ya que nos recuerda una especie de colador que atrapa todas las cosas malas y pasa 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 inducidos, 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 de la máquina autoconsciente se crea con facilidad. Wesley Crusher creó uno por accidente. También Richard Daystrom. La computadora Enterprise D cocinó a Moriarty en sus ciclos libres, el Dr. Farallon creó los Exocomps, y así sucesivamente. Todo lo que parece tener que hacer es construir algo equivalente a un sistema de demostración de teoremas y dejar que funcione lo suficiente como para tropezar con la prueba de que P o alguna otra clase manejable es equivalente a NP y el sistema está listo para las carreras.

O quizás 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 de manera eficiente los problemas completos de PSPACE.

+1 por usar evidencia del mundo para mostrar algo. El mas excelente.
Creo que simplemente abordan los tres puntos que usted plantea mediante la potencia informática bruta. Un DTM puede resolver precisamente los mismos problemas que un NTM, pero lleva más tiempo. Entonces, si sus habilidades de ingeniería son lo suficientemente locas, pueden toser 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 Quizás debería haber escrito que P = NP te permite descifrar todo lo que es útil, excepto los pads de una sola vez. Si no puede verificar el descifrado en tiempo polinomial, que es lo que significa tener un criptosistema fuera de NP, entonces _ incluso con la clave_ el descifrado no es computacionalmente factible. Eso para mí no es un criptosistema útil.
@bitmask: En algún lugar de los manuales técnicos, 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 hay * hay * 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 por sí mismo es una evidencia muy fuerte 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 computación ND significativamente más potente parece ser pequeña (pero, claro, 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 poner una fecha a esto?
@AncientSwordRage ¿Fecha a qué?
@Kyle la fecha en la que crees que la serie Star Trek se representó por primera vez como P = NP.
@AncientSwordRage Escogiendo entre mis ejemplos, creo que tendría que ser el primer episodio que presenta 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 que lo convierte en 1966, que es un contendiente.¿Se opondría a que lo edite en su respuesta?
@AncientSwordRage no, adelante.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

Anticuerpos, Charles Stross, 2000

Una historia corta que se basa en el hecho de que resolver P = NP es un requisito previo necesario para desarrollar una inteligencia informática. Está disponible en su libro Toast . Stross ha publicado 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 para 2000. Seleccionado para el Premio Theodore Sturgeon de 2001 (perdido ante "La historia de Tendoleo" de Ian MacDonald).

#3
+25
deworde
2011-09-26 04:42:50 UTC
view on stackexchange narkive permalink

El otro libro de Stross que trata de esto es The Atrocity Archives, donde Alan Turing resolvió P = NP, pero luego descubrieron que al hacerlo permitían el acceso a Cthonic Realms, por lo que ahora una rama completa of Government existe para evitar que este descubrimiento se convierta en de conocimiento público.

#4
+18
Mike Scott
2011-01-13 13:20:03 UTC
view on stackexchange narkive permalink

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 ), la computación es más fácil en algunas partes de la galaxia, lo que permite cosas como la inteligencia artificial y los viajes FTL.

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

¿Existe alguna evidencia indirecta? Lo que recuerdo es que el cálculo es diferente fuera de la Zona Lenta (la tesis de Church solo se sostiene en la Zona Lenta) y algo como P = NP no tiene por qué aplicarse o incluso tener sentido allí.
En * A Fire Upon the Deep *, los Skode Riders encuentran graciosa la creencia de Pham en el cifrado de claves públicas. De eso podemos concluir que `P == NP` en 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 confían los algoritmos de cifrado de clave pública más extendidos (factorización, registro discreto) no son (se cree) NP-completas. Estos son los problemas que las computadoras cuánticas son teóricamente capaces de resolver en el tiempo polinomial. Dicho esto, existen algoritmos de cifrado de clave pública que * están * basados ​​en problemas NP-complete, pero estos no son de uso generalizado (todavía ...)
@BlueRaja Actualmente no conocemos forma de usar una computadora cuántica para resolver problemas NP completos de manera eficiente, pero usted está afirmando que `P
@Code: Sí, lo siento, no hablé con cuidado. Quiero 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, ya que es posible que _en cualquier lugar particular de una zona_, nuestra intuición de que puede construir un problema NP que no puede resolver fácilmente sea cierta. Pero creo que es lo suficientemente similar como para que valga la pena mencionarlo, ya que puede moverse (o enviar un mensaje) a una zona más alta, donde su problema se podrá resolver fácilmente.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

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 números primos grandes utilizando esta máquina, con un resultado algo extraño. Por lo tanto, no está completamente dado que NP = P , pero parece probable.

Eso no tiene sentido. Un problema pertenece a P, si existe una determinada 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 bucles de tiempo, Harry superó la pregunta de P = NP.
Sí, si su prueba tuvo éxito, habría significado que existe un dispositivo de cálculo "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á sujeta a la autoconsistencia de Novikov.Todavía es posible que P = PSPACE para las máquinas de Turing ordinarias, pero esto se considera incluso menos plausible que P = NP por los teóricos de la complejidad 'convencionales'.
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

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 están accediendo mentalmente a universos alternos, y al aplicar las ecuaciones adecuadas, uno podría viajar a ese universo alterno y traer la mente de la persona de regreso a nuestro universo. Fue un ejercicio intelectual que el protagonista principal Harold Shea decide poner a prueba. En broma se refiere a viajar a través de syllogismobile, 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 va desde allí. Toda la serie Enchanter los hace saltar por el universo a través de la mitología, los cuentos de hadas y las obras clásicas al hacerlo.

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

#7
+1
Gelvis
2011-01-13 22:16:51 UTC
view on stackexchange narkive permalink

Nemesis, Isaac Asimov, 1989

Habla sobre 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.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

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 que la inteligencia humana permanece inalterada. Además, los objetos físicos tienden a autooptimizarse: un trineo de madera desarrolla lubricante para deslizarse fácilmente por la carretera. Este efecto de práctica puede ser impulsado 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 polinómico (buscando una variedad casi infinita de posibles soluciones en un corto período de tiempo). . Este universo en realidad trasciende P = NP.

Por favor [editar] por qué cree que este es el caso.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

En la historia Starshield Sentinels de Margaret Weis y Tracy Hickman, había computadoras / inteligencias artificiales que podían responder cualquier pregunta instantáneamente enviando la pregunta al pasado. , dándole 'tiempo' para resolverlo. El único inconveniente fue que la computadora tenía 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 / solve en la pregunta.

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

#10
-2
Michael Kohne
2011-09-27 06:38:38 UTC
view on stackexchange narkive permalink

Si no me equivoco, en ' The Ragged Astronauts' de Bob Shaw, uno de los personajes dedica un poco de tiempo a explicar a otro cómo pi es 3. 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; de lo contrario, era una historia ordenada).

¿Cómo se relaciona esto con p = np?


Esta pregunta y respuesta fue traducida automáticamente del idioma inglés.El contenido original está disponible en stackexchange, a quien agradecemos la licencia cc by-sa 2.0 bajo la que se distribuye.
Loading...