El enigma de hoy ilumina uno de los grandes éxitos de la informática teórica, un resultado sorprendente que incluso ha dejado Los expertos en el campo se sorprendieron..

Llegaremos a este resultado (el teorema de PCP) más tarde. Pero primero, ¡vamos al desafío!

Es un rompecabezas de palabras. Cada pista estilo crucigrama apunta a una columna vertical. La respuesta a cada pista es una palabra de tres letras, formada por las tres letras a las que apunta la pista.

Resolvamos esto juntos. ¿Un animal con tres letras? ¿Qué tal «murciélago»?

Cada vez que conseguimos dar una respuesta convincente, ganamos un punto por cada letra. “Bat” nos da una puntuación de 3.

Ahora continuemos. Esta es una forma de completar la cuadrícula.

Las letras rojas son las que no están incluidas en la solución.

Tenga en cuenta que esta cuadrícula no es una solución completa. Las tres pistas principales han sido plenamente respondidas. Resalté las flechas verdes en la pista «verbo», que apunta a «pagar». Pero las tres pistas inferiores sólo se resolvieron parcialmente. La comida apunta a «pey», no a «guisante». Sin embargo, podemos darnos un punto por cualquier letra de una respuesta potencialmente correcta, por lo que 'pey' nos da 2 puntos por las dos letras correctas en 'pea'. Puntuación total: 15 puntos.

Así es como puedes obtener una solución completa, con una puntuación máxima de 18. ¡Por supuesto, “gato” era un punto de partida mucho más obvio!

Te Puede Interesar:   Misterioso dodecaedro romano se exhibirá en Lincoln | Bretaña romana

La conclusión de este enigma, dice Dana Moshkovitz, profesora de informática de la Universidad de Texas en Austin, es que «está bien obtener una solución parcial». De hecho, eso es lo que lo hace divertido. El objetivo es conseguir la mayor puntuación posible.

A continuación se muestran tres ejemplos, en orden de dificultad creciente.

Problema 1

Problema 2

En este acertijo, las pistas son más ambiguas: algunas pistas son sinónimos de la respuesta y otras son descripciones de la respuesta. Por tanto, 'exclamación' se refiere a una exclamación.

Problema 3

Ahora las pistas son aún más ambiguas.

Regresaré a las 5 p. m. en el Reino Unido con soluciones completas. (Posiblemente existan muchas soluciones completas). Mientras tanto, NO HAY SPOILERS. Por favor, analice sus palabras favoritas de tres letras.

(Si algún lector emprendedor desea crear una versión interactiva de este rompecabezas, enlace a continuación).

Entonces, ¿qué tienen que ver estos acertijos con uno de los resultados más importantes de la informática? Para aguantar.

Hace cincuenta años, los científicos informáticos descubrieron que muchos problemas que ocurren naturalmente, como cuál es la mejor manera de apilar maletas de diferentes tamaños en el maletero de un automóvil, se vuelven tan complejos cuando se amplían que las computadoras no pueden resolverlos de un vistazo. . Sorprendentemente, también resulta que obtener respuestas aproximadas a estos problemas de la maleta en el maletero es igualmente difícil.

Te Puede Interesar:   Una noche soy una asesina y la siguiente noche mi marido tiene una aventura. ¿Por qué tenemos los sueños que alcanzamos? | Dormir

La analogía actual del rompecabezas es que el rompecabezas tiene una solución correcta, pero también tiene soluciones “aproximadas”. Como vimos, puedes obtener puntuación total y también puntuación parcial. Imagínate si ampliaras este tipo de rompecabezas con más pistas, letras y flechas. Distinguir los acertijos que brindan una solución perfecta de aquellos que brindan una solución parcial es tan complejo que las computadoras no pueden hacerlo en un tiempo razonable.

Este campo –el estudio de la “dureza de aproximación”– tiene profundas conexiones con el teorema PCP, un resultado impresionante en cuanto a demostraciones matemáticas. Normalmente, cuando desea verificar una prueba matemática, debe verificarla línea por línea para ver si hay algún error. Como cuando un profesor analiza tu trabajo para asegurarse de que cada deducción sea un paso lógico.

Sin embargo, el teorema PCP muestra que no es necesario comprobar una prueba línea por línea para asegurarse de que no haya errores. En lugar de ello, puedes reescribir la prueba de tal manera que puedas comprobarla eligiendo al azar sólo dos o tres bits de la prueba y comprobando sólo esos bits, es decir, comprobando en dos o tres puntos si el bit es un 0 o un 1. ¡Solo unas pocas piezas! ¡Para cualquier prueba matemática!

Te Puede Interesar:   Investigadores estudian la actividad cerebral de los cirujanos en busca de signos de sobrecarga cognitiva | Investigación médica

El acertijo anterior es una versión simplificada del teorema PCP, dice Dana Moshkovitz, quien lo creó como una forma de presentar el tema a sus alumnos. Y añade: “Prácticamente *todos* los resultados conocidos que tenemos hoy sobre la dureza de la aproximación comienzan con el teorema PCP en forma de rompecabezas”.

Sí, esto es un poco confuso, ya que el acertijo de palabras no se trata de verificar evidencia. Sin embargo, puedes ver el enlace si consideras cada palabra esencialmente como una “verificación” de una solución completa.

El teorema PCP (las letras significan prueba probabilísticamente verificable) fue un gran avance teórico y promete importantes aplicaciones prácticas. Por ejemplo, permite que una computadora con poca memoria verifique de manera muy eficiente si una computadora grande hizo algo correctamente, como, por ejemplo, un iPhone que verifica la integridad de un programa en la nube. Esta tecnología ya se está utilizando en blockchains, como El unicornio tecnológico israelí StarkWare.

Si desea obtener más información sobre el teorema de PCP, Aquí hay una gran pieza de Dana. Esto fue en XRDS, la revista estudiantil de la Association for Computing Machinery.

Actualmente soy comunicador científico residente en el Instituto Simons de Teoría de la Computación de la Universidad de California, Berkeley.

He estado haciendo un rompecabezas aquí cada dos lunes desde 2015. Siempre estoy buscando grandes rompecabezas. Si quieres sugerir alguno, envíame un correo electrónico.

Deja un comentario