RT info:eu-repo/semantics/bachelorThesis
T1 Sobre la conjetura de la sensibilidad y su resolución vía teoría de grafos
A1 Asensio Ferrero, Sara
A2 Universidad de Valladolid. Facultad de Ciencias
K1 Sensibilidad
K1 Complejidad
K1 Grafos
K1 Funciones booleanas
AB 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 elenfoque matemático dentro de esta disciplina, restringiéndonos al caso de las funciones booleanas. Para ellas, definiremos algunas de las medidas decomplejidad 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ó probarla equivalencia de todas ellas, y esto se consiguió demostrando la llamada conjetura de la sensibilidad, que recibe este nombre en honor a una de lasmedidas 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 unaconexión potente y bonita con la teoría de la complejidad.
YR 2022
FD 2022
LK https://uvadoc.uva.es/handle/10324/57957
UL https://uvadoc.uva.es/handle/10324/57957
LA spa
NO Departamento de Algebra, Geometría y Topología
DS UVaDOC
RD 16-jul-2024