2026-05-05T18:24:47Zhttps://uvadoc.uva.es/oai/request

oai:uvadoc.uva.es:10324/579572023-12-04T14:44:22Zcom_10324_38col_10324_852

Giménez, Philippe Thierry Universidad de Valladolid. Facultad de Ciencias Asensio Ferrero, Sara 2022 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. application/pdf https://uvadoc.uva.es/handle/10324/57957 spa Sobre la conjetura de la sensibilidad y su resolución vía teoría de grafos info:eu-repo/semantics/bachelorThesis TEXT UVaDOC. Repositorio Documental de la Universidad de Valladolid Hispana