9 votos

Cajas de embalaje y prueba de la hipótesis de Riemann

De Scott Aaronson del blog:

Hay un número finito (y no inimaginablemente grande) conjunto de cuadros, que si sabíamos cómo empacar los cajas en el maletero de su coche, entonces también nos gustaría saber una prueba de la Riemann Hipótesis. En efecto, cada prueba formal de la Hipótesis de Riemann con en la mayoría de los (decir) de un millón de símbolos corresponde a alguna forma de embalaje de las cajas en su tronco, y viceversa. Además, una lista de los cuadros y sus dimensiones pueden ser factible escrito abajo.

Su posterior comentó a explicar de dónde sacó esto de: "3-dimensional bin-packing es NP-completo."

No veo cómo estos dos están relacionados.

Otra pregunta inspirado por el mismo artículo está aquí.

1voto

Mike Powell Puntos 2913

La cuestión de si una prueba formal de la Hipótesis de Riemann existe (con más de un millón de símbolos) es un problema en NP: dado tal prueba, puede ser verificada a ser correcta en el polinomio de tiempo.

Bin-packing es NP-completo: esto significa que todo problema en NP se puede reducir a la bandeja de embalaje. En particular, el problema mencionado en el párrafo anterior puede. (Esta es una reducción que puede ser explícito, así que una vez que especificar la prueba verificador etc., podemos llevar a cabo los pasos de la reducción para obtener una instancia de bin packing. También la necesidad de la reducción a ser "parsimonioso", es decir, las soluciones se corresponden uno a uno; creo que lo es).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X