Teorema de sensibilidad

En complejidad computacional , el teorema de sensibilidad , demostrado por Hao Huang en 2019, ^{[ 1 ]} establece que la sensibilidad de una función booleana${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$es al menos la raíz cuadrada de su grado , resolviendo así una conjetura planteada por Nisan y Szegedy en 1992. ^{[ 2 ]} La demostración es notablemente concisa, dado que el progreso previo había sido limitado. ^{[ 3 ]}

Varios artículos de finales de la década de 1980 y principios de la de 1990 ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} demostraron que varias medidas de complejidad de árboles de decisión de funciones booleanas están relacionadas polinómicamente, lo que significa que si${\displaystyle \alpha (f),\beta (f)}$Entonces, existen dos medidas de este tipo.${\displaystyle \alpha (f)\leq C\beta (f)^{C}}$por alguna constante${\displaystyle C>0}$Nisan y Szegedy ^{[ 2 ]} demostraron que el grado y el grado aproximado también están relacionados polinómicamente con todas estas medidas. Su demostración se basó en otra medida de complejidad, la sensibilidad de bloques , que había sido introducida por Nisan. ^{[ 7 ]} La ​​sensibilidad de bloques generaliza una medida más natural, la sensibilidad (crítica), que había aparecido anteriormente. ^{[ 8 ] [ 9 ] [ 10 ]}

Nisan y Szegedy preguntaron ^{[ 11 ]} si la sensibilidad de bloque está acotada polinómicamente por la sensibilidad (la otra dirección es inmediata, ya que la sensibilidad es como máximo la sensibilidad de bloque). Esto equivale a preguntar si la sensibilidad está relacionada polinómicamente con las diversas medidas de complejidad de los árboles de decisión, así como con el grado, el grado aproximado y otras medidas de complejidad que, a lo largo de los años, han demostrado estar relacionadas polinómicamente con estas. ^{[ 12 ]} Esto se conoció como la conjetura de la sensibilidad. ^{[ 13 ]}

A lo largo de los años, se demostraron varios casos especiales de la conjetura de sensibilidad. ^{[ 14 ] [ 15 ]} El teorema de sensibilidad fue finalmente demostrado en su totalidad por Huang, ^{[ 1 ]} utilizando una reducción de Gotsman y Linial. ^{[ 16 ]}

Cada función booleana${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$puede expresarse de una manera única como un polinomio multilineal . El grado de${\displaystyle f}$es el grado de este polinomio único, denotado${\displaystyle \deg(f)}$.

La sensibilidad de la función booleana${\displaystyle f}$en ese punto${\displaystyle x\in \{0,1\}^{n}}$es el número de índices${\displaystyle i\in [n]}$de tal manera que${\displaystyle f(x^{\oplus i})\neq f(x)}$, dónde${\displaystyle x^{\oplus i}}$se obtiene de${\displaystyle x}$volteando el${\displaystyle i}$coordenada 'th. La sensibilidad de${\displaystyle f}$es la sensibilidad máxima de${\displaystyle f}$en cualquier momento${\displaystyle x\in \{0,1\}^{n}}$, denotado${\displaystyle s(f)}$.

El teorema de sensibilidad establece que

${\displaystyle s(f)\geq {\sqrt {\deg(f)}}.}$

En la otra dirección, Tal, ^{[ 17 ]} mejorando una cota anterior de Nisan y Szegedy, ^{[ 2 ]} demostró que

${\displaystyle s(f)\leq \deg(f)^{2}.}$

El teorema de sensibilidad es estricto para la función AND-de-OR: ^{[ 18 ]}

${\displaystyle \bigwedge _{i=1}^{m}\bigvee _{j=1}^{m}x_{ij}}$

Esta función tiene grado${\displaystyle m^{2}}$y sensibilidad${\displaystyle m}$.

Dejar${\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}$ser una función booleana de grado${\displaystyle d}$. Consideremos cualquier maxinomio de${\displaystyle f}$, es decir, un monomio de grado${\displaystyle d}$en el polinomio multilineal único que representa${\displaystyle f}$Si sustituimos un valor arbitrario en las coordenadas que no se mencionan en el monomio, entonces obtenemos una función.${\displaystyle F}$en${\displaystyle d}$coordenadas que tiene grado${\displaystyle d}$y además,${\displaystyle s(f)\geq s(F)}$. Si demostramos el teorema de sensibilidad para${\displaystyle F}$entonces sigue siendo para${\displaystyle f}$. Así pues, de ahora en adelante, asumimos sin pérdida de generalidad que${\displaystyle f}$tiene título${\displaystyle n}$.

Defina una nueva función${\displaystyle g\colon \{0,1\}^{n}\to \{0,1\}}$por

${\displaystyle g(x_{1},\dots ,x_{n})=f\oplus x_{1}\oplus \cdots \oplus x_{n}.}$

Se puede demostrar que desde${\displaystyle f}$tiene título${\displaystyle n}$entonces${\displaystyle g}$está desequilibrado (lo que significa que${\displaystyle |g^{-1}(0)|\neq |g^{-1}(1)|}$), decir${\displaystyle |g^{-1}(1)|>2^{n-1}}$. Consideremos el subgrafo${\displaystyle G}$del hipercubo (el gráfico en${\displaystyle \{0,1\}^{n}}$en el que dos vértices están conectados si difieren en una sola coordenada) inducido por${\displaystyle S=g^{-1}(1)}$Para demostrar el teorema de sensibilidad, basta con mostrar que${\displaystyle G}$tiene un vértice cuyo grado es al menos${\displaystyle {\sqrt {n}}}$Esta reducción se debe a Gotsman y Linial. ^{[ 16 ]}

Huang ^{[ 1 ]} construye una signatura del hipercubo en la que el producto de los signos a lo largo de cualquier cuadrado es${\displaystyle -1}$Esto significa que existe una manera de asignar un signo a cada arista del hipercubo de forma que se cumpla esta propiedad. Ahmadi et al. ^{[ 19 ]} ya habían encontrado este mismo método de asignación de signos en grafos con pocos autovalores distintos.

Dejar${\displaystyle A}$Sea la matriz de adyacencia con signo correspondiente a la firma. La propiedad de que el producto de los signos en cada casilla es${\displaystyle -1}$implica que${\displaystyle A^{2}=nI}$y por lo tanto la mitad de los valores propios de${\displaystyle A}$son${\displaystyle {\sqrt {n}}}$y la mitad son${\displaystyle -{\sqrt {n}}}$. En particular, el espacio propio de${\displaystyle {\sqrt {n}}}$(que tiene dimensión${\displaystyle 2^{n-1}}$) interseca el espacio de vectores soportados por${\displaystyle S}$(que tiene dimensión${\displaystyle >2^{n-1}}$), lo que implica que hay un vector propio${\displaystyle v}$de${\displaystyle A}$con valor propio${\displaystyle {\sqrt {n}}}$que se apoya en${\displaystyle S}$(Esta es una simplificación del argumento original de Huang debido a Shalev Ben-David. ^{[ 20 ]} )

Consideremos un punto${\displaystyle x\in S}$maximizar${\displaystyle |v_{x}|}$Por un lado,${\displaystyle Av={\sqrt {n}}v}$. Por otro lado,${\displaystyle Av}$es como máximo la suma de los valores absolutos de todos los vecinos de${\displaystyle x}$en${\displaystyle S}$, que es como máximo${\displaystyle \deg _{G}(x)\cdot |v_{x}|}$. Por eso${\displaystyle \deg _{G}(x)\geq {\sqrt {n}}}$.

El teorema de sensibilidad puede reformularse de forma equivalente como

${\displaystyle \deg(f)\leq s(f)^{2}.}$

Laplante et al. ^{[ 21 ]} refinaron esto a

${\displaystyle \deg(f)\leq s_{0}(f)s_{1}(f),}$

dónde${\displaystyle s_{b}(f)}$es la sensibilidad máxima de${\displaystyle f}$en un punto en${\displaystyle f^{-1}(b)}$Además, demostraron que este límite se alcanza en dos puntos vecinos del hipercubo.

Aaronson, Ben-David, Kothari, Rao y Tal ^{[ 22 ]} definieron una nueva medida, la sensibilidad espectral de${\displaystyle f}$, denotado${\displaystyle \lambda (f)}$. Este es el mayor valor propio de la matriz de adyacencia del gráfico de sensibilidad de${\displaystyle f}$, que es el subgrafo del hipercubo que consta de todas las aristas sensibles (aristas que conectan dos puntos${\displaystyle x,y}$de tal manera que${\displaystyle f(x)\neq f(y)}$). Demostraron que la prueba de Huang se puede descomponer en dos pasos:

• ${\displaystyle \deg(f)\leq \lambda (f)^{2}}$.
• ${\displaystyle \lambda (f)\leq s(f)}$.

Utilizando esta medida, demostraron varias relaciones estrechas entre las medidas de complejidad de las funciones booleanas:${\displaystyle \deg(f)=O(Q(f)^{2})}$y${\displaystyle D(f)=O(Q(f)^{4})}$. Aquí${\displaystyle D(f)}$es la complejidad de consulta determinista y${\displaystyle Q(f)}$es la complejidad de la consulta cuántica.

Dafni et al. ^{[ 23 ]} extendieron las nociones de grado y sensibilidad a funciones booleanas en el grupo simétrico y en el esquema de asociación de emparejamiento perfecto , y demostraron análogos del teorema de sensibilidad para dichas funciones. Sus demostraciones utilizan una reducción al teorema de sensibilidad de Huang.

• Modelo de árbol de decisión

• Aaronson, Scott; Ben-David, Shalev; Kothari, Robin; Rao, Shravas; Tal, Avishay (15 de junio de 2021). Grado vs. grado aproximado e implicaciones cuánticas del teorema de sensibilidad de Huang . ACM. págs. 1330–1342 . arXiv : 2010.12629 . doi : 10.1145/3406325.3451047 . ISBN  978-1-4503-8053-9.
• Ahmadi, Bahmán; Alinaghipour, Fatemeh; Cavers, Michael S.; Fallat, Shaun; Más pobre, Karen; Nasserasr, Shahla (septiembre de 2013). "Número mínimo de valores propios distintos de gráficos". Revista Electrónica de Álgebra Lineal . 26 . Sociedad Internacional de Álgebra Lineal: 673– 691. arXiv : 1304.1205 . doi : 10.13001/1081-3810.1679 . ISSN 1081-3810 . 
• Bafna, Mitali; Lokam, Satyanarayana V.; Tavenas, Sébastien; Velingker, Ameya; Faliszewski, Piotr; Muscholl, Anca; Niedermeier, Rolf (2016). "Sobre la conjetura de sensibilidad de las fórmulas Read -k ". 41º Simposio Internacional sobre Fundamentos Matemáticos de la Informática (MFCS 2016) . pag.  14 páginas. doi : 10.4230/LIPICS.MFCS.2016.16 . ISSN 1868-8969 . 
• Dafni, Neta; Filmus, Yuval; Lifshitz, Noam; Lindzey, Nathan; Vinyals, Marc; Lee, James R. (2021). "Medidas de complejidad en el grupo simétrico y más allá (Resumen extendido)". 12.ª conferencia Innovations in Theoretical Computer Science (ITCS) .  5 páginas, 326343 bytes. doi : 10.4230/LIPICS.ITCS.2021.87 . ISSN 1868-8969 . 
• Ben-David, Shalev (3 de julio de 2019). "Comentario n.º 35 sobre la conjetura de sensibilidad resuelta" .
• Blum, Manuel; Impagliazzo, Russell (1987). "Oráculos genéricos y clases de oráculos". 28º Simposio Anual sobre Fundamentos de la Informática (sfcs 1987) . IEEE. doi : 10.1109/sfcs.1987.30 .
• Buhrman, Harry; de Wolf, Ronald (2002). "Medidas de complejidad y complejidad de árboles de decisión: una revisión". Theoretical Computer Science . 288 (1). Elsevier BV: 21– 43. doi : 10.1016/s0304-3975(01)00144-x . ISSN 0304-3975 . 
• CS, Karthik; Tavenas, Sébastien; Lal, Akash; Akshay, S.; Saurabh, Saket; Sen, Sandeep (2016). "Sobre la conjetura de sensibilidad para formas normales disyuntivas". 36.ª Conferencia Anual de la IARCS sobre Fundamentos de la Tecnología del Software y la Informática Teórica (FSTTCS 2016) .  15 páginas. doi : 10.4230/LIPICS.FSTTCS.2016.15 . ISSN 1868-8969 . 
• Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger (1986). "Límites de tiempo superiores e inferiores para máquinas de acceso aleatorio paralelas sin escrituras simultáneas". SIAM Journal on Computing . 15 (1): 87– 97. doi : 10.1137/0215006 . ISSN 0097-5397 . 
• Gotsman, Chaim; Linial, Nati (1992). "La equivalencia de dos problemas en el cubo" . Journal of Combinatorial Theory, Serie A. 61 ( 1). Elsevier BV: 142–146 . doi : 10.1016/0097-3165(92)90060-8 . ISSN 0097-3165 . 
• Hartmanis, Juris; Hemachandra, Lane A. (1991). "Funciones unidireccionales y el no isomorfismo de conjuntos NP-completos" . Theoretical Computer Science . 81 (1): 155– 163. doi : 10.1016/0304-3975(91)90323-T .
• Hatami, Pooya; Kulkarni, Raghav; Pankrátov, Denis (2011). "Variaciones sobre la conjetura de la sensibilidad" . Teoría de la Computación . 1 (1): 1– 27. doi : 10.4086/toc.gs.2011.004 . ISSN 1557-2862 . 
• Huang, Hao (1 de noviembre de 2019). "Subgrafos inducidos de hipercubos y una demostración de la Conjetura de Sensibilidad". Annals of Mathematics . 190 (3). arXiv : 1907.00847 . doi : 10.4007/annals.2019.190.3.6 . ISSN 0003-486X . 
• Klarreich, Erica (25 de julio de 2019). "Resuelta en dos páginas una conjetura de la informática con décadas de antigüedad" . Quanta Magazine .
• Laplante, Sophie; Naserasr, Reza; Sunny, Anupa; Wang, Zhouningxin (2023-03-07). "Conjetura de sensibilidad e hipercubos con signo" . Archivo abierto HAL . Recuperado el 25 de abril de 2024 .
• Nisan, Noam (1991). "CREW PRAMs y árboles de decisión". SIAM Journal on Computing . 20 (6): 999– 1007. doi : 10.1137/0220062 . ISSN 0097-5397 . 
• Nisan, Noam; Szegedy, Mario (1994). "Sobre el grado de las funciones booleanas como polinomios reales". Computational Complexity . 4 (4): 301– 313. doi : 10.1007/BF01263419 . ISSN 1016-3328 . 
• Simon, Hans-Ulrich (1983). "Una cota ajustada Ω(loglog n) para el tiempo de cálculo de funciones booleanas no degeneradas mediante RAM paralelas". Fundamentos de la teoría de la computación . Notas de clase en ciencias de la computación. Vol.  158. Berlín, Heidelberg: Springer Berlin Heidelberg. págs. 439–444 . doi : 10.1007/3-540-12689-9_124 . ISBN  978-3-540-12689-8.
• Tal, Avishay (09/01/2013). «Propiedades y aplicaciones de la composición de funciones booleanas». ITCS '13: Actas de la 4.ª conferencia sobre innovaciones en informática teórica . ACM. doi : 10.1145/2422436.2422485 . ISBN 978-1-4503-1859-4.
• Tardos, G. (1989). "Complejidad de las consultas, o por qué es difícil separar${\displaystyle NP^{A}\cap coNP^{A}}$de${\displaystyle P^{A}}$por oráculos aleatorios${\displaystyle A}$?". Combinatorica . 9 (4): 385– 392. doi : 10.1007/BF02125350 . ISSN 0209-9683 . 
• Wegener, Ingo (1987). La complejidad de las funciones booleanas . Stuttgart Chichester Nueva York Brisbane [etc.]: John Wiley & Sons. ISBN 0-471-91555-6.