Sobre la conjetura de la sensibilidad y su resolución vía teoría de grafos

Abstract

La teoría de la complejidad computacional es una de las grandes áreas dentro de las ciencias de la computación. En este trabajo, expondremos el enfoque matemático dentro de esta disciplina, restringiéndonos al caso de las funciones booleanas. Para ellas, definiremos algunas de las medidas de complejidad más interesantes y probaremos que todas ellas son equivalentes, en el sentido de que están polinómicamente relacionadas. Aunque desde 1994 se conoce gran parte de estas relaciones entre medidas de complejidad de funciones booleanas, hasta 2019 no se consiguió probar la equivalencia de todas ellas, y esto se consiguió demostrando la llamada conjetura de la sensibilidad, que recibe este nombre en honor a una de las medidas estudiadas. En su demostración juega un papel muy importante la teoría de grafos, que abre nuevas líneas de investigación y muestra una conexión potente y bonita con la teoría de la complejidad.