Explicando SAT a los profesores de ciencias de la escuela secundaria

9

Soy un estudiante de segundo año de secundaria que está interesado en ciencias de la computación. Desarrollé un algoritmo genial para #SAT, y estoy implementando y haciendo un proyecto de feria de ciencias al respecto. Mi asesora, quien es la mejor maestra de ciencias en mi escuela y también es maestra de AP Comp Sci, me dijo que no tiene absolutamente ninguna idea de qué se trata mi proyecto, y que necesito poder explicarle brevemente por qué #SAT es importante en menos de 5 minutos. Le dije que SAT se reduce a #SAT e intenté explicar por qué SAT es importante: le di algunos ejemplos de problemas de NP, le expliqué cómo los problemas de NP se reducen a SAT y le expliqué cómo con la búsqueda binaria puede reducir ciertos problemas de optimización a SAT , que le permite plegar proteínas y crear potentes modelos de IA. Desafortunadamente, ella no me entendió en absoluto. ¿Podrías darme algunos consejos?

PD: Mi asesor me preguntó qué problemas útiles se reducen a #SAT que no se reducen a SAT (suponiendo que algunos problemas en #P sean más difíciles que sus versiones NP correspondientes). Todo lo que se me ocurrió fue encontrar cuántos modelos para un conjunto de datos dado son mejores que un modelo dado (suponiendo que cada parámetro del modelo sea más pequeño que un número dado de bits). Busqué otros en la web pero no pude encontrar nada que pudiera entender. ¿Hay alguna otra buena aplicación?

Elliot Gorokhovsky
fuente
2
El permanente (incluso para matrices cuyas entradas están restringidas a 0 o 1) es # P-complete, por lo que cualquier aplicación del permanente también es una aplicación de su algoritmo, siempre que estas aplicaciones requieran que calcule (o se aproxime) el permanente de alguna matriz "en la práctica" (en lugar de en papel).
Yuval Filmus
Has elegido un excelente proyecto teórico pero bastante avanzado / abstracto para la escuela secundaria. Una pregunta obvia, ¿cómo aprendiste sobre la importancia de #SAT? puede haber algunos vínculos con, por ejemplo, el plan de estudios AP CS a través de la completitud NP, etc., ¿ya ha tomado esa clase? ¿Qué libro de texto usa? si es buena, habrá algunas conexiones con la mía allí. sugiero visitar el Computer Science Chat para obtener más consejos, varios estudiantes de posgrado / doctorado pasan el rato allí. Y también lo invito a un salón de belleza para discutirlo más a fondo.
vzn
Si tuviera que explicárselo a una audiencia que no sea CS / no matemática, yo: (1) explicaría qué es un problema (espera un cierto tipo de entrada y desea producir una salida basada en esa entrada), ( 2) explique lo que significa que un problema sea difícil, (3) explique los problemas SAT y #SAT, (4) establezca que estos problemas son difíciles y (5) establezca que encontrar algoritmos más rápidos para problemas en general se valora mucho suficiente para que haya un premio de un millón de dólares si puede resolver el SAT rápidamente. Espero que ayude un poco, aunque no responda totalmente a sus preguntas. ¡Que tengas un buen día!
Michael Wehar
Hay algunos problemas enumerados en wikipedia (aunque probablemente ya lo haya visto). Aquí está el enlace: en.wikipedia.org/wiki/Sharp-P
Michael Wehar
1
@MichaelWehar ¡Aunque si pudieras resolver SAT rápidamente, ese millón de dólares no valdría mucho para ti!
Elliot Gorokhovsky

Respuestas:

6

El permanente es # P-completo, incluso cuando está restringido a matrices con valores . El permanente se puede usar para calcular ciertos parámetros en mecánica estadística, ver por ejemplo este documento sobre el problema de cobertura del dímero. Como no soy físico, no puedo comentar si estos problemas teóricos de mecánica estadística son realmente útiles; Sospecho que no son directamente útiles, pero el área en sí podría conducir a ideas útiles. También podría darse el caso de que algunos de estos parámetros sean útiles por sí solos, pero tendrá que consultar con un experto.{0,1}

Su lanzamiento de 5 minutos podría ser algo como esto:

La mecánica estadística es una parte hermosa y profunda de la física y la química que estudia cómo el comportamiento emergente de los grandes sistemas resulta de leyes físicas microscópicas que operan en elementos individuales. Explica fenómenos como las leyes de los gases, la magnetización y las transiciones entre diferentes fases de la materia. La mecánica estadística está íntimamente relacionada con la teoría de la probabilidad, la informática, la investigación de operaciones y la ciencia de datos.

Muchas cantidades importantes en mecánica estadística pueden formularse como instancias de #SAT. Por lo tanto, un algoritmo para resolver #SAT exactamente o aproximadamente se puede utilizar para predecir fenómenos físicos y químicos.

Esto podría exagerar un poco el caso, pero así es como funcionan los argumentos de venta.

Yuval Filmus
fuente
1

Esta pregunta parece mezclar SAT y #SAT un poco en su redacción. Sí, los dos están muy unidos. #SAT se define simplemente como la clase de complejidad asociada con contar el número de soluciones a un problema SAT y se conjetura ampliamente que es mucho más difícil, pero quizás sorprendentemente, no se ha demostrado . #SAT ni siquiera se estudia mucho en teoría de la complejidad a nivel universitario, es más un tema de investigación teórica avanzada.

Una forma de motivar la importancia de #SAT es a través del teorema de Toda, que ganó un premio Gödel en 1998 por su profunda importancia. De Wikipedia:

Por lo tanto, el teorema de Toda implica que para cualquier problema en la jerarquía polinómica hay una reducción determinista de Turing en tiempo polinómico a un problema de conteo. [1]

Además, dado que SAT y #SAT ni siquiera han demostrado tener una complejidad diferente, se puede establecer un caso razonable de que comprender la complejidad de #SAT podría conducir a una idea del problema P vs NP , que tiene mucha información y motivación .

vzn
fuente
re P vs NP ver también el libro reciente de Fortnow Golden ticket, P / NP y la búsqueda de lo imposible
vzn
Cualquier aplicación de SAT es una aplicación de #SAT, estoy buscando aplicaciones de ambos.
Elliot Gorokhovsky
jajaja entonces tu pregunta es muy diferente. Los problemas completos de NP tienen aplicaciones extremadamente amplias y esto está ampliamente documentado. vea el libro de Fortnows o, por ejemplo, la teoría de Garey / Johnson sobre la integridad de NP . y, por cierto, si el maestro de AP CS no sabe lo completo que es NP, entonces debe ser despedido.
vzn
Bueno, los niños que toman la clase ni siquiera entienden conceptos simples como la búsqueda binaria, de modo que si ella lo supiera, de todos modos se desperdiciaría en los oídos de los estudiantes.
Elliot Gorokhovsky
Además, ¿puedes explicar por qué es difícil probar el teorema de Toda? Porque dado que todos los problemas en NP se reducen a SAT, que trivialmente se reduce a #SAT. ¿Qué problemas hay en PH que no están en NP? Lo siento, he aprendido todo de Wikipedia, así que tengo muchos agujeros en mi conocimiento.
Elliot Gorokhovsky