¿Cuáles serían las implicaciones en el mundo real de una prueba constructiva

56

Tengo una comprensión de alto nivel del problema y entiendo que si se "probara" absolutamente que es cierto con una solución provista, se abriría la puerta para resolver numerosos problemas dentro del ámbito de la informática.P=NP

Mi pregunta es, si alguien publicara una prueba indiscutible y constructiva de , ¿cuáles son algunos de los efectos inmediatos que veríamos de tal descubrimiento? P=NP

No estoy pidiendo puntos de vista obstinados sobre cómo sería el mundo en 5-10 años. En cambio, tengo entendido que este es un problema tan fundamentalmente insoluble que podría cambiar radicalmente la forma en que calculamos ... muchas cosas (sí, aquí es donde se muestra mi ignorancia ...) que no podemos calcular fácilmente hoy .

¿Qué tipo de efecto casi inmediato tendría una prueba exhaustiva, precisa y constructiva de en el mundo práctico?P=NP

RLH
fuente
55
En el peor de los casos, es posible que no haya efectos prácticos (aparte de que los autores se hagan famosos), si la prueba no es constructiva, lo que significa que alguien solo prueba que existen det. algoritmos pol-time para los problemas NP-completos sin proporcionar uno realmente.
lukas.coenig
2
Mi cosa favorita a considerar en este escenario hipotético es el hecho de que la optimización se vuelve fácil. Un caso específico sería que encontrar parámetros que son MLE globales para cualquier modelo probabilístico se volvería trivial. Por ejemplo, esto afectaría inmediatamente a los investigadores en genética y otras ciencias al permitirles estimar mejor los parámetros subyacentes para sus modelos.
Nicholas Mancuso
Vale la pena mencionar lo que esperaría que fuera la alternativa más probable en el escenario poco probable de que P = NP: es decir, que se encuentra una prueba de que ningún problema en NP puede fallar en P, pero sin ningún ejemplo de algoritmo P para un NP- problema completo El hecho de que alguien pueda demostrar que debe existir alguna solución en P no significa que realmente podamos encontrar esa solución ni verificar su corrección. Irónicamente, esa última parte podría ser más fácil de hacer si existiera un algoritmo P para un problema de NPC, pero bueno, eso es un problema de huevo y gallina ...
Eamon Nerbonne
55
El bit "constructivo" es un arenque rojo. Existe un programa específico bien conocido que resuelve SAT en tiempo polinómico si f (esencialmente se une en todos los solucionadores SAT). Por lo tanto, una prueba clásica de ya garantiza que este solucionador SAT particular esté en , por lo que también obtenemos una prueba constructiva. P = N P PP=NPP=NPP
Andrej Bauer

Respuestas:

34

La gente ha dado buenas respuestas suponiendo que con alguna constante realmente grande. Voy a jugar al optimista y asumir que encontramos una prueba de P = N P con una constante muy pequeña. Tal vez no sea probable, pero voy a tratar de dar una idea de qué tipo de cosas sucederían si podíamos resolver de manera eficiente todas las N P problemas.P=NPP=NPNP

  • Compiladores: algunos programas de computadora serían un poco más rápidos, ya que los compiladores usan colores de gráficos para la asignación de registros. Podríamos asignar exactamente un gran número de registros. Los compiladores existentes que usan una solución aproximada (como los gráficos cordales) obtendrían mejores resultados, y los que usan una solución exacta serían más rápidos.

  • Ubicación de la instalación: las empresas podrían encontrar el lugar óptimo para colocar fábricas y depósitos de suministros para enviar a sus tiendas, cuando posiblemente haya miles de tiendas y fábricas. Probablemente no sería una gran mejora con respecto a las aproximaciones modernas, pero reduciría los costos.

  • Compra de boletos de avión: los boletos de avión son raros ya que no siguen la igualdad triangular. A veces es más barato volar desde A -> B -> C que directamente desde A -> C, algo que no aparece al modelar distancias. Sería fácil crear un sitio web que encuentre la secuencia más barata de vuelos que visiten varias ciudades y comience y termine en su ciudad natal.

  • Diseño del circuito: los circuitos eléctricos en un chip son básicamente fórmulas booleanas. Cosas como la minimización podrían calcularse de manera eficiente, por lo que nuestro hardware sería un poco más eficiente.

  • Programación: ¿enojado porque su escuela puso dos de sus exámenes al mismo tiempo? Si su escuela podría saber cuántos intervalos de tiempo necesitan para que ningún estudiante tenga un conflicto, o si se le da un número de intervalos de tiempo, minimice la cantidad de conflictos.P=NP

Esto es solo una muestra de aplicaciones prácticas que veríamos si la completitud de no fuera una barrera. Estoy seguro de que me he perdido muchos, pero si la construcción dada tuviera una buena constante, las implicaciones serían de gran alcance.NP

jmite
fuente
55
Citando de Wikipedia en P vs NP : If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found.Soy consciente de que esto podría no referirse a las aplicaciones prácticas, pero definitivamente parece una exageración si lo comparo con su respuesta. ¿De qué está hablando realmente?
Nik Kyriakides
44
@Nicholas Un poco de hipérbole pero puedo ver el punto. Para ser increíblemente impreciso: los problemas NPsignifican que podemos verificar si una solución es correcta en el tiempo polinómico, pero un problema Psignifica que podemos encontrar una solución en el tiempo polinómico. Si NP=Pesto significa que es el mismo esfuerzo verificar si una solución es correcta o encontrar una solución. Sin embargo, esto ignora por completo los factores constantes, que obviamente hacen una gran diferencia en la realidad.
Voo
2
¿Puedes mencionar los efectos de las aplicaciones criptográficas?
ζ--
55
Si P = NP, entonces las factorizaciones primas serían computables en el tiempo polinómico (se sabe que la factorización prima es verificable en el tiempo polinómico). Muchos algoritmos criptográficos, como el RSA increíblemente común, se basan en la dificultad de calcular las factorizaciones principales. Si la "constante" antes mencionada es lo suficientemente pequeña, todas las encriptaciones RSA, independientemente del tamaño de la clave, podrían volverse inútiles al instante.
user2407038
3
Usted enfatiza que está hablando de P = NP "con una constante muy pequeña" y lo compara con "podríamos resolver de manera eficiente todos los problemas de NP". Si su noción de eficiencia incluye constantes pequeñas, el teorema de la jerarquía del tiempo ya lo hace imposible: hay problemas que se pueden resolver en el tiempo que no se pueden resolver en n 99 , y mucho menos n 2 o n log n . n100n99n2nlogn
David Richerby
30

No veremos necesariamente ningún efecto. Suponga que alguien encuentra un algoritmo que resuelve 3SAT en variables en 2 100 n operaciones básicas. No podrá ejecutar este algoritmo en ninguna instancia, ya que lleva demasiado tiempo. O suponga que encuentra un algoritmo que se ejecuta en n 100 operaciones básicas. Solo podremos usarlo en instancias de 3SAT en una sola variable, ya que para más variables lleva demasiado tiempo.n2100nn100

Por otro lado, suponga que P NP, y que incluso la hipótesis del tiempo exponencial más fuerte es válida. Entonces, en general, 3SAT no debe ser manejable. Sin embargo, los solucionadores de SAT parecen estar bien en ciertos problemas.

¿Que esta pasando aqui? Hay varios problemas con la pregunta P vs. NP:

  1. Solo se refiere al peor de los casos.
  2. Es solo asintótico.
  3. Todos los límites de tiempo polinómicos son iguales.

Estos problemas ponen en duda su relevancia para el mundo real. Ahora podría suceder que se encuentre un algoritmo realmente rápido para 3SAT, tan rápido que incluso el cifrado simétrico podría romperse. Pero considero esto altamente improbable. Por otro lado, es perfectamente consistente que P sea diferente de NP mientras que el factoring es práctico; eso rompería ciertos esquemas de cifrado de clave pública. Esta es una situación probable que tendría repercusiones, pero no está relacionada con la pregunta P vs. NP.

La pregunta P vs. NP podría ser natural desde un punto de vista matemático, pero su relevancia práctica es dudosa, en mi opinión. La investigación sobre la cuestión, por otro lado, podría o no tener repercusiones prácticas; no se guía por este aspecto.

Yuval Filmus
fuente
2
Una prueba podría no incluir un algoritmo P para un problema NPC, pero si lo hiciera, la consecuencia práctica sería que de repente vale la pena buscar los problemas NP específicos (o más bien, ahora problemas P) que tienen valor a grandes escalas y también constantes manejables Actualmente, tener NP completo tiende a significar que probablemente no valga la pena mirarlo. Entonces, la consecuencia práctica del mundo real dependería de cómo se muestre que NP es P: esperaría una prueba que permita la construcción de un algoritmo P para un problema de NPC, y todo depende de los detalles de ese algoritmo.
Eamon Nerbonne
Si tiene una solución de 2 ^ 100n para 3SAT, con mucho gusto lo haré en la placa ASIC y amenazaré con romper el RSA-2048 en el tiempo suficiente para hacer que los certificados raíz de 30 años sean una mala idea.
Joshua
11

Incluso sin P = NP, las computadoras de hoy son increíblemente poderosas.


Editar 22 de enero de 2018 Ahora descubrí cómo debería haber "interpretado" el texto citado en el ejemplo a continuación. Fue mi culpa, el elemento inverso debía ser único . Aquí está mi archivo de entrada del 22 de diciembre de 2014 ( addinvrig.in ) y aquí está el archivo de entrada fijo de hoy ( addinvrigFixed.in ). La línea crucial es que (x+(-x))+((-y)+y)=((-y)+y)+(x+(-x)).el poder de las herramientas de razonamiento automatizadas en sí mismas sigue siendo fascinante para mí, incluso si no pueden salvarme de malinterpretar los escritos de otras personas.

El uso de herramientas de razonamiento automatizado es sorprendentemente útil para mí, cuando me encuentro con teoremas citados donde no estoy seguro de cómo "interpretar" el texto :



x,yS(xy)=xy=xyxy=xy
aaSSaaSS

Adapté mis archivos de entrada prover9 para este teorema, e inmediatamente se me mostró un contraejemplo para el teorema como se citó. La modificación leve de los supuestos produjo muchos teoremas verdaderos similares, lo que hace que sea más probable que Karvellas haya declarado y demostrado un teorema correcto, que aquí solo se citó incorrectamente. Buscar en Google la referencia de este teorema solo arrojó otro artículo que citaba a Karvellas aún menos preciso .


Esta es una colección increíblemente incompleta de resultados asistidos por computadora para problemas específicos que son intratables en general si P! = NP. Tal vez esta colección deja claro al menos a algunos lectores que todos tendemos a subestimar los poderes de las computadoras en este dominio. Muchas otras respuestas a esta pregunta parecen sugerir que no habría grandes consecuencias si las computadoras mejoraran (ligeramente) en la resolución de problemas insolubles. Pero las computadoras mejoran en la resolución de problemas intratables todo el tiempo (porque se gasta bastante tiempo y dinero para que esto suceda), y esto tiene consecuencias muy reales. Si se probara P = NP, entonces tal vez aumentaría la conciencia de lo que las computadoras realmente pueden hacer (incluso hoy), y más personas usarían computadoras para ayudarlos con tales tareas. (PD: estoy convencido de que P! = NP,

Thomas Klimpel
fuente
7

Hay muchas opiniones sobre las implicaciones del mundo real de P = NP. Como se ve en otras buenas respuestas, hay principalmente 2 escuelas de pensamiento. Una es que un algoritmo de tiempo P puede ser muy difícil o inviable de implementar debido a "anomalías inesperadas" asociadas con la abstracción. p.ej:

  • el programa puede ser demasiado "grande" para codificar realmente
  • podría haber una constante muy grande involucrada de tal manera que para todas las instancias al alcance de la "computación terrestre", todavía son de larga duración, es decir, la eficiencia no "entra en juego", excepto en instancias muy grandes. se sabe que algunos algoritmos realmente encajan en este caso como señaló recientemente Knuth (pregunta 15)

En general, estoy buscando un mayor enfoque en algoritmos que funcionen rápido con respecto a problemas cuyo tamaño, n, es factible. La mayor parte de la literatura actual está dedicada a algoritmos que son asintóticamente excelentes, pero son útiles solo cuando n excede el tamaño del universo.

Impagliazzo realiza un famoso estudio de caso como lo cita J. en otra respuesta. Sin embargo, su ensayo ha sido extrapolado de alguna manera mientras tanto. Aquí hay una gran referencia nueva de un experto que aborda esta pregunta en una especie de escenario futuro de ciencia ficción, ch2 / p11. resumiendo

El boleto dorado: P, NP y la búsqueda de lo imposible por Lance Fortnow

  • "Si resulta que P = NP y tenemos algoritmos eficientes para todos los problemas de NP, el mundo cambiará de manera que haga que Internet parezca una nota al pie de la historia. No solo sería imposible describir todos estos cambios sino también Las mayores implicaciones de las nuevas tecnologías serían imposibles de predecir ".

  • Algoritmo implementado rápidamente en supercomputadora. Boeing contrata de inmediato para obtener un mejor diseño de ala para un nuevo avión que le permita volar sin escalas desde Londres a Sydney.

  • El algoritmo de búsqueda utilizado para encontrar un nuevo algoritmo que sea aún más rápido, optimiza la solución original P = NP. Finaliza con el resultado de 42 millones de líneas de código ininteligible. Llamado el "algoritmo Urbana"

  • Algoritmo utilizado para encontrar tratamientos personalizados para el cáncer / curas casi adaptadas a las personas. cura el cáncer, el SIDA, la diabetes, pero el resfriado común sigue siendo un misterio

  • El algoritmo de súper programación permite a los pronosticadores "hacer avances increíbles en la predicción del clima, permitiendo predicciones precisas de temperatura, vientos, nubosidad y precipitación casi un año antes. Algoritmos similares ahora salvan vidas al predecir con precisión tormentas, tornados, huracanes para que la gente pueda preparar o evacuar según sea necesario ".

  • Reconocimiento facial altamente preciso

  • La computadora puede reconstruir modelos 3D de una escena en tiempo real desde diferentes ángulos de cámara

  • Los algoritmos informáticos controlan las operaciones de la cámara para eventos deportivos (en lugar de ser controlados por humanos)

  • El algoritmo genera comentarios y repeticiones automatizadas que incluyen ángulos y estadísticas bien elegidos, y se generan en cualquier idioma en tiempo real

  • El béisbol / deporte de fantasía adquiere una nueva dimensión con simulaciones altamente precisas

  • Recetas de comida mejoradas por el algoritmo

  • El algoritmo podría usarse para "aprender casi cualquier cosa, incluyendo lo que hace buen arte, música popular y palabras que conmueven el alma. Recuerde que P = NP significa que lo que podemos probar, podemos encontrarlo. Entonces, una vez que tenga un algoritmo proceso para reconocer la grandeza, puede usar el algoritmo nuevamente para encontrar rápidamente esa grandeza ".

  • El político utiliza un algoritmo informático para reconocer grandes discursos y generar uno que se ajuste a los patrones. El discurso se vuelve viral en internet.

  • Las personas generan obras de arte completas a partir de arte incompleto / inacabado, por ejemplo, sinfonías. usan algoritmos para generar nuevos registros de Beatles / Elvis. Nuevo arte, novelas, obras de teatro y poesía, por ejemplo, comedia romántica con Humphrey Bogart / Julia Roberts.

  • Amazon puede crear novelas personalizadas para personas bajo demanda. NBC crea series de televisión de acción y aventura en vivo creadas completamente por computadora

  • Realidad virtual simulada en videojuegos que permite cualquier acción de los jugadores en lugar de un conjunto fijo de posibles argumentos.

  • La policía usa el algoritmo como "una herramienta increíble para resolver crímenes, aparentemente haciendo lo imposible para localizar a los sospechosos". El algoritmo informático puede reconstruir caras probables (para bocetos compuestos) utilizando solo ADN. La policía compara a un sospechoso de asesinato utilizando una búsqueda masiva de la base de datos de fotos de la licencia de conducir alineada con el boceto generado (del ADN).

Desafortunadamente, no mucho de lo que Fortnow describe anteriormente está respaldado por la literatura científica real, excepto tal vez una extrapolación imaginativa de los mundos Impagliazzos. Se necesitaría mucho más para diseccionar este punto por punto, pero para resumir, todo parece ser entretenido pero fantástico / ilusorio (o tal vez ese es su punto oculto). De hecho, hay principios científicos que están en conflicto con muchos de los elementos. Y observe que Fortnow es un fanático de los deportes, por lo que desarrolla una metáfora extendida en esa área, pero ¿podría esto ser más una indicación de que los humanos piensan en surcos ?

Por ejemplo, se sabe que el "efecto mariposa" implica que la predicción meteorológica precisa más allá de un (digamos) horizonte de varios días es imposible debido a la "dependencia sensible de las condiciones iniciales" (y Fortnow admitió más tarde en su blog que criticó repetidamente exactamente esto punto). Además, existe una gran cantidad de evidencia de que las computadoras fallan en tareas altamente subjetivas para los humanos, como generar o identificar arte influyente (una tarea en la que incluso los humanos expertos no tienen éxito consistentemente).

En realidad, toda la cuestión está rayando en contrafactual o una premisa falsa . Tenga en cuenta que una gran mayoría de científicos expertos encuestados piensan / creen, a pesar de la falta de pruebas incontrovertibles hasta ahora, P ≠ NP. y es natural compararlo con otras leyes / restricciones / limitaciones conocidas como la termodinámica (por ejemplo, imposibilidad de movimiento perpetuo / energía libre ) y estadísticas, por ejemplo, el teorema del "no almuerzo gratis" .

Entonces, la conclusión es que quizás incluso los científicos expertos no pueden predecir exactamente el resultado de P = NP. Entonces, quizás la mejor respuesta por ahora es admitir que los humanos no tienen una buena respuesta en este momento.

vzn
fuente
1
nota: las 2 escuelas de pensamiento son "P = NP podría no ser un gran problema" a "sería un gran problema" con Fortnow representando la última posición. pero en realidad ambas escuelas de pensamiento están fuera del favor de la hipótesis / conjetura CS convencional. en otras palabras (como ha señalado aaronson ) no es el tipo de pregunta que puede abordarse, por ejemplo, simplemente como Equipo A vs Equipo B. la preponderancia de evidencia científica parece indicar P ≠ NP ...
vzn
1
+1 para el libro de Fortnow. Lo iba a sugerir yo mismo. Una lista más corta de implicaciones (impresionantes) de P = NP se encuentra en cacm.acm.org/magazines/2009/9/… (también por Fortnow).
Fizz
7

P vs. NP, técnicamente vs. moralmente

Como dijo Yuval, es posible que P = NP sea técnicamente cierto pero moralmente falso. P = NP es moralmente cierto (incluso si no es necesariamente técnicamente) si hay un algoritmo determinista rápido (digamos , o tal vez incluso O ( n lg nO(n2)O(nlgn)265536+21024n256O(nlgn)

Entonces, ¿qué sucede si P = NP es moralmente cierto?

QQcierto, entonces todos estos problemas pueden resolverse muy rápido. Solo para dar un ejemplo, puede aprender los mejores pesos para modelos de aprendizaje automático muy complicados. Puede romper los protocolos de cifrado.

Si sabe que desea resolver un problema de NP completo no en entradas generales sino en entradas con propiedades particulares, no necesita preocuparse por el problema general. Solo necesita resolver el problema más simple. Desafortunadamente, a menudo no es fácil determinar qué tipo de entradas le interesan en la práctica.

Aún así, la heurística puede funcionar increíblemente bien en la práctica, como vemos con SAT o Programación de enteros o Machine Learning. (El aprendizaje PAC usando el modelo muy simple de 3-DNFs es intratable si NP

Kaveh
fuente
3

¿Qué tipo de efecto casi inmediato tendría una prueba exhaustiva y precisa de P = NP, con una solución proporcionada, en el mundo práctico?

Es probable que surjan muchas cosas buenas, pero a nadie le importaría.

El problema es que la base de (casi) todo el cifrado moderno se basa en el supuesto de que P no igual a NP. El cifrado que protege su contraseña a medida que pasa por Internet y se guarda en las bases de datos. El cifrado que protege los datos de la tarjeta de crédito a medida que pasa por Internet ... El cifrado que protege los miles de millones de transacciones financieras diarias que vinculan nuestra economía global al organismo gigante que es.

Mejor caso, P = NP significa que se detiene. La gente vuelve a usar efectivo y los bancos intentan registrar estos retiros de efectivo en algún medio desconectado ya que las transacciones a una oficina central ya no son confiables. Esto dura unos pocos meses hasta que se implemente una mejor encriptación a nivel mundial. Mejor caso.

En el peor de los casos, P = NP significa que alguien rompe el mundo. La moneda se basa en el concepto de confianza. Usted valora un dólar, porque confía en que su vecino le dará bienes o servicios por un dólar. Usted valora su computadora diciendo que tiene 500 dólares en el banco, porque puede deslizar su tarjeta y obtener 500 dólares en bienes y servicios ...

¿Y si no pudieras confiar en eso? Si P = NP, alguien podría hacerse pasar por varios bancos, gobiernos, personas y aleatorizar efectivamente la cantidad de moneda en cada cuenta. Eliminar la moneda en cada cuenta. Claro, varios bancos tienen copias de seguridad para justificarlo, pero ¿por cuánto tiempo se ha roto su cifrado? ¿Qué transacciones fueron buenas y cuáles fueron suplantadas? Es imposible saberlo.

Una vez que se rompe esa confianza, se produce el caos. Cualquier beneficio de poder lidiar con el problema del vendedor ambulante (por ejemplo) se ignora a medida que las personas luchan por alimentarse.

Es probable que la realidad esté en algún punto intermedio, pero con suerte esto representa una imagen lo suficientemente grande de cuán importante es este problema.

Telastyn
fuente
44
Crypto no estaría tan roto como parece sugerir. Incluso si P = NP, no puede predecir determinísticamente los bits generados aleatoriamente (por ejemplo, claves). Esta es la razón por la cual el pad de una vez siempre funcionará. Los supuestos de dureza computacional solo ayudan a justificar el uso de claves más cortas y esquemas asimétricos.
mdxn
2
@mdx: ha pasado un tiempo desde que lo estudié en profundidad, pero ¿no importa si puedes predecir las teclas si puedes decodificarlas de manera rápida y fácil?
Telastyn
Para la criptografía de clave privada, lo ideal es tratar de difundir la aleatoriedad del mensaje de una manera que sea difícil de deshacer. El beneficio de esto es que podemos usar teclas más cortas, ser eficientes en tiempo / espacio y aún así lograr una buena seguridad. Si un atacante prácticamente puede deshacer esto, entonces esto no sucede. Si P = NP, entonces tendríamos que basar la seguridad en problemas más difíciles. La desventaja es que el cifrado y descifrado también es computacionalmente más difícil.
mdxn
Si bien un esquema de clave privada aún puede retener la seguridad teórica de la información de la aleatoriedad de la clave, un sistema de clave pública no lo hará. Esa es la situación en la que podría extraer la clave. Nuevamente, en el mundo donde P = NP, podemos usar un problema más difícil para basar su seguridad si tenemos uno. También sería menos eficiente.
mdxn
1
@mdx: los pads únicos no son una solución viable para las necesidades de tráfico de Internet, porque el pad debe entregarse de forma segura al destinatario antes de que pueda usarse, y ahora acaba de retrasar el problema un paso.
Mason Wheeler
2

Se producirá una caída masiva en el costo de los equipos, la electricidad y los enfoques de nube. Muchas cosas se están calculando con la fuerza bruta en este momento, o con aproximaciones que todavía usan algo de fuerza bruta pesada. Ya no haremos todos esos cálculos de fuerza bruta paralizados masivamente.

De ninguna manera es el único uso de la computación en la nube, pero seguirá siendo un factor notable en el uso de energía, el procesamiento en la nube, etc. Solo el ahorro de energía podría ser notable en nuestra huella de carbono.

La IA también será mucho mejor. Finalmente, podemos tener una computadora que puede ser el mejor jugador de GO, y su calculadora gráfica le ganará en el ajedrez.

dsollen
fuente
44
n×n19×19n×n
Usted está asumiendo que los problemas que actualmente resolvemos por fuerza bruta caen en NP, y todos ellos se vuelven instantáneamente manejables. Esto está lejos de ser cierto.
Yves Daoust
0

NP y encontramos soluciones donde eran críticas (como soluciones aproximadas).

Y la conjetura que se refuta no significa que todos los problemas de utilidad práctica se resolverían en un chasquido de dedos. En primer lugar, aún pueden ser más difíciles que NP.

Yves Daoust
fuente
-1 porque su argumento no depende de ningún detalle del sistema sobre el que se supone que está razonando. Con el mismo argumento, aprendimos a vivir en un mundo sin automóviles, por lo que no esperaría que los automóviles causen una revolución. Por el contrario, aprendimos a vivir en un mundo sin zapatos para reproducir MP3, por lo que no esperaría que causaran una revolución. Uno de estos ejemplos es claramente falso, el otro probablemente sea cierto. Su conclusión sobre P vs NP podría ser cualquiera.
David Richerby
@DavidRicherby: gracias por explicar el voto negativo.
Yves Daoust