Los límites ...
De hecho, tenemos N F A ( L ) ≥ C o v ( M ) + C o v ( N ) , ver Teorema 4 en (Gruber y Holzer 2006). Para un límite superior, tenemos 2 C o v ( M ) + C o v ( N ) ≥ D F A ( L ) ≥ N F A ( L ) , vea el Teorema 11 en el mismo documento. NFA(L)≥Cov(M)+Cov(N)2Cov(M)+Cov(N)≥DFA(L)≥NFA(L)
... no se puede mejorar sustancialmente
Puede haber una brecha subexponencial entre C o v ( M ) + C o v ( N ) y N F A ( L ) . El siguiente ejemplo, y la prueba de la brecha, es una adaptación de un ejemplo similar que ilustra las limitaciones de los protocolos de dos partes para probar límites inferiores en la complejidad del estado no determinista de (Hromkovič et al. 2009):Cov(M)+Cov(N)NFA(L)
Usamos el alfabeto [ n ] = {1 , 2 , ... , n} . Deje L = {[ n ] = {1 , 2 , ... , n}x y z ∈ [ n ] 3 ∣ x = y ∨ x ≠ z} .L={xyz∈[n]3∣x=y∨x≠z}
Primero nos ocupamos de C o v ( M ) . Observe que si w = x y z con y = z , entonces
w ∈ L : en caso de que x = y , w ∈ L y en caso de x ≠ y , también tenemos
x ≠ z y por lo tanto w ∈ L . Además, si w tiene la forma x y z con
y ≠ z , entoncesCov(M)w=xyzy=zw∈Lx=yw∈Lx≠yx≠zw∈Lwxyzy≠zw ∈ L iff x ≠ z . Entonces podemos escribir L = L ′ ∪ L ″ , con L ′ = { x y z ∈ [ n ] 3 ∣ y = z } y L ″ = {w∈Lx≠zL=L′∪L′′L′={xyz∈[n]3∣y=z}x y z ∈ [ n ] 3 ∣ y ≠ z ∧ x ≠ z} .L′′={xyz∈[n]3∣y≠z∧x≠z}
Ahora considere los gráficos bipartitos G ′ = ( U ′ , V ′ , E ′ ) con U ′ = [ n ] , V ′ = { y z ∈ [ n ] 2 ∣ y = z } , E ′ = U ′ × V ′ , Así como G ″ = ( U ″ , V ″G′=(U′,V′,E′)U′=[n]V′={yz∈[n]2∣y=z}E′=U′×V′, E ″ ) con U ″ = [ n ] , V ″ = { y z ∈ [ n ] 2 ∣ y ≠ z } ,
E ″ = { ( x , y z ) ∣ x ≠ z } , y G = ( U ′ ∪ U ″ , V ′ ∪ V ″ ,G′′=(U′′,V′′,E′′)U′′=[n]V′′={yz∈[n]2∣y≠z}E′′={(x,yz)∣x≠z}E ′ ∪ E ″ ) . Luego, unacubierta de borde bicliquepara el gráfico
G da lugar a una cubierta de M consubmatrices monocromáticas 1 , y viceversa (Teorema 21 en Gruber y Holzer 2006).G=(U′∪U′′,V′∪V′′,E′∪E′′)GM1
Un simple truco de kernelization para calcular una cubierta de borde biclique para G '
es colocar los vértices gemelos desde U ' en clases de equivalencia. Luego hacemos lo mismo en el gráfico resultante para los vértices gemelos de V ' . Los vértices gemelos son aquellos con vecindad idéntica. Este paso no altera el número mínimo de bicliques necesarios para cubrir todos los bordes en el gráfico respectivo.G′U′V′
El paso de kernelization colapsa G ' en un gráfico con dos vértices y un solo borde. Por lo tanto, los bordes de G ' pueden cubrirse con un solo biclique. Al aplicar el paso de kernelization a G ″ se obtiene un gráfico de corona
en 2 n vértices, cuya dimensión bipartita (el número mínimo de cubierta del borde biclique) se sabe que es σ ( n ) , donde σ es la función inversa del coeficiente binomial medio (De Caen et al.1981). Observe que σ ( n ) = O ( log nG′G′G′′2nσ(n)σ) . Por lo tanto, la dimensión bipartita de G es 1 + σ ( n ) , que es idéntica a C o v ( M ) .σ(n)=O(logn)G1+σ(n)Cov(M)
Ahora considere C o v ( N ) . Observe que si w = x y z con x = y , a continuación, w ∈ L . Si x ≠ y , entonces x ∈ L iff x ≠ z . Entonces podemos escribir L = L ‴ ∪ L ⁗
con L ‴ = { x y z ∈ [ n ] 3 ∣ xCov(N)w=xyzx=yw∈Lx≠yx∈Lx≠zL=L′′′∪L′′′′= y } y L ⁗ = { x y z ∈ [ n ] 3 ∣ x ≠ y ∧ x ≠ z } . Casi el mismo argumento que el anterior produce
C o v ( N ) = 1 + σ ( n ) .L′′′={xyz∈[n]3∣x=y}L′′′′={xyz∈[n]3∣x≠y∧x≠z}Cov(N)=1+σ(n)
Queda por dar una cota inferior de la complejidad del estado no determinista de L . Observe que L contiene todas las palabras de la forma x x x
con x ∈ [ n ] . Para cada tal palabra x x x fijar una aceptación de cálculo de un NFA mínimo aceptar L . Supongamos que p x denota el estado alcanzado después de leer el prefijo x , y que q x denota el estado alcanzado después de leer el prefijo x x de la palabra de entrada x x x . Entonces todos los paresLLxxxx∈[n]xxxLpxxqxxxxxx( p x , q x ) debe ser diferente. En aras de la contradicción, suponga ( p x , q x ) = ( p y , q y )
para algunos x ≠ y . Entonces podemos construir un cálculo de aceptación en la entrada x y x , de modo que el NFA esté en estado p x = q x después de leer el prefijo x , y en estado q y = q x(px,qx)(px,qx)=(py,qy)x≠yxyxpx=qxxdespués de leer el prefijo x y . Pero la cadena x y x no está en L . Para el conjunto de estados Q de la NFA, esto muestra que | Q | 2 ≥ n . Por lo tanto, para n grande , obtenemos una separación subexponencial entre C o v ( M ) + C o v ( N ) y | Q | (la complejidad del estado no determinista de L ).
Referencias
Dominique de Caen, David A. Gregory, Norman J. Pullman: El rango booleano de las matrices cero-uno, en: Cadogan, Charles C. (ed.), Tercera Conferencia del Caribe sobre Combinatoria e Informática, Departamento de Matemáticas, Universidad de los Indias Occidentales, págs. 169-173 (1981)
Hermann Gruber y Markus Holzer. Encontrar límites más bajos para la complejidad del estado no determinista es difícil . Informe TR06-027, Coloquio electrónico sobre la complejidad computacional (ECCC), marzo de 2006. Apareció una versión corta en: Oscar H. Ibarra y Zhe Dang, editores, 10ª Conferencia internacional sobre desarrollos en teoría del lenguaje (DLT 2006), Santa Bárbara (CA) , EE. UU., Volumen 4036 de LNCS, páginas 363-374. Springer, junio de 2006.
Juraj Hromkovic, Holger Petersen, Georg Schnitger: sobre los límites de la técnica de complejidad de la comunicación para probar límites inferiores en el tamaño de los NFA mínimos . Theor Comput Sci. 410 (30–32): 2972–2981 (2009)