La conjetura de la sensibilidad ha sido demostrada

Por Francisco R. Villatoro, el 28 julio, 2019. Categoría(s): Ciencia • Informática • Matemáticas • Mathematics • Noticias • Science

La conjetura de la sensibilidad  es un resultado de la teoría de la complejidad computacional propuesto en 1989 por Nisan y Szegedy. Su enunciado es tan sencillo que parece demostrable en una sola página; pero este logro se ha resistido durante 30 años. El matemático Hao Huang (Univ. Emory, Atlanta, EE UU) ha logrado demostrarla en una página y media (su artículo tiene seis páginas). Su demostración se basa en un resultado publicado en 1992 por Gotsman y Linial. Siendo tan sencilla, y usando un resultado tan antiguo, parece imposible que no se le hubiera ocurrido a nadie más (Huang afirma que le ha costado unos 7 años de trabajo). Por cierto, Huang ha demostrado una generalización de la conjetura; para la conjetura original basta una página, como ha mostrado Shalev Ben-David.

La conjetura relaciona la sensibilidad s(f) de una función booleana f con su sensibilidad a bloques bs(f). En concreto, afirma que, para toda función booleana f, existe una constante C>0 tal que bs(f) ≤ s(f)C. Huang ha demostrado que bs(f) ≤ 2 s(f)4; más aún, ha demostrado la conjetura más general de Gotsman y Linial de 1992 que afirma que s(f) ≥ (deg(f))1/2. Una función booleana f: {0,1}n → {0,1} devuelve un dígito binario para cada una de las 2n  entradas posibles de n dígitos binarios (cada entrada se puede escribir como un vértice de un cubo en n dimensiones). Su sensibilidad s(f) es el máximo de sus sensibilidades s(f,x) para cada una de las entradas posibles; la sensibilidad s(f,x) el número máximo de dígitos binarios de x que se pueden cambiar sin alterar el resultado de f(x) (se pueden interpretar estos cambios como un grafo entre los vértices de un cubo en n dimensiones). La sensibilidad a bloques bs(f) es el máximo de sus sensibilidades a bloques bs(f,x), siendo éstas el número máximo de bloques de índices disjuntos B1, B2, …, Bk, tales que f(x) ≠ f(xBi), donde xBi es el vector binario x con todos los índices en Bi cambiados. Obviamente, bs(f) ≥ s(f), habiendo varios resultados de complejidad computacional que apuntaban a que la relación entre ambas era polinómica. Por cierto, el grado de una función booleana, deg(f), es el grado del polinomio real multinomial (que es único) que la representa.

Los interesados en los detalles de la demostración, que es fácil de entender si ya se conocía su enunciado, así como los conceptos de subgrafo inducido y autovalor, pueden disfrutarla en Hao Huang, “Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture,” arXiv:1907.00847 [math.CO] (01 Jul 2019). Una presentación divulgativa para matemáticos en Scott Aaronson, “Sensitivity Conjecture resolved,” Shtetl-Optimized, 02 Jul 2019; sobre la relación entre el grado y la sensibilidad recomiendo Lance Fortnow, “Degree and Sensitivity,” Computational Complexity, 11 Jul 2019; las consecuencias del nuevo teorema no han tardado en llegar, como R. J. Lipton, K. W. Regan, “Discrepancy Games and Sensitivity,” Gödel’s Lost Letter and P=NP, 25 Jul 2019; y Terence TaoTwisted convolution and the sensitivity conjecture,” What’s new, 26 Jul 2019.

Para legos recomiendo Lance Fortnow, “Local Kid Makes History,” Computational Complexity, 02 Jul 2019; y Erica Klarreich, “Decades-Old Computer Science Conjecture Solved in Two Pages,” Quanta Magazine, 25 Jul 2019.

[PS 30 Jul 2019] Recomiendo la demostración de solo media página, basada en la de Shalev Ben-David, pero igual de fácil de entender, de Donald Knuth, “A computational proof of Huang’s degree theorem,” Stanford, 28 Jul 2019 [PDF]. [/PS]

Esta figura de Lucy Reading-Ikkanda para Quanta Magazine ilustra la relación entre funciones booleanas y vértices de hipercubos, así como la relación entre subgrafos en hipercubos y la sensibilidad de la función. Siendo autoexplicativa, creo que no requiere más comentarios.



Deja un comentario