NC (complejidad)

Problema sin resolver en informática

⁠

{\mathsf {NC}}{\overset {?}{=}}{\mathsf {P}}

⁠

Más problemas sin resolver en informática

En la teoría de la complejidad computacional , la clase NC (por "Clase de Nick") es el conjunto de problemas de decisión decidibles en tiempo polilogarítmico en una computadora paralela con un número polinomial de procesadores. En otras palabras, un problema con tamaño de entrada n está en NC si existen constantes c y k tales que puede resolverse en tiempo $O ((log n) c)$ usando $O (n k)$ procesadores paralelos. Stephen Cook ^{[ 1 ]}^{[ 2 ]} acuñó el nombre "Clase de Nick" en honor a Nick Pippenger , quien había realizado una extensa investigación ^{[ 3 ]} sobre circuitos con profundidad polilogarítmica y tamaño polinomial. ^{[ 4 ]} Como en el caso de la teoría de la complejidad de circuitos , generalmente la clase tiene una restricción adicional de que la familia de circuitos debe ser uniforme ( ver más abajo ).

Así como la clase P puede considerarse como los problemas tratables ( tesis de Cobham ), NC puede considerarse como los problemas que pueden resolverse eficientemente en una computadora paralela. ^{[ 5 ]} NC es un subconjunto de P porque los cálculos paralelos polilogarítmicos pueden simularse mediante cálculos secuenciales de tiempo polinomial. Se desconoce si NC = P , pero la mayoría de los investigadores sospechan que esto es falso, lo que significa que probablemente existan algunos problemas tratables que son "inherentemente secuenciales" y no pueden acelerarse significativamente mediante el paralelismo. Así como la clase NP-completa puede considerarse como "probablemente intratable", la clase P-completa , al utilizar reducciones NC , puede considerarse como "probablemente no paralelizable" o "probablemente inherentemente secuencial".

En la definición, se puede asumir que la computadora paralela es una máquina de acceso aleatorio paralelo ( PRAM ). Se trata de una computadora paralela con un conjunto central de memoria, donde cualquier procesador puede acceder a cualquier bit de memoria en tiempo constante. La definición de NC no se ve afectada por la forma en que la PRAM gestiona el acceso simultáneo a un solo bit por parte de más de un procesador. Puede ser CRCW, CREW o EREW. Consulte la documentación de PRAM para obtener descripciones de estos modelos.

De forma equivalente, NC se puede definir como aquellos problemas de decisión decidibles por un circuito booleano uniforme (que se puede calcular a partir de la longitud de la entrada; para NC, suponemos que podemos calcular el circuito booleano de tamaño n en espacio logarítmico en n ) con profundidad polilogarítmica y un número polinomial de puertas con un fan-in máximo de 2.

RNC es una clase que extiende NC con acceso a la aleatoriedad.

Problemas en Carolina del Norte

Al igual que con P , mediante un ligero abuso del lenguaje, se podría clasificar los problemas de funciones y los problemas de búsqueda como pertenecientes a NC . Se sabe que NC incluye muchos problemas, entre ellos:

Suma, multiplicación y división de números enteros;
Multiplicación de matrices , determinante, inversa , rango;
MCD polinomial, mediante una reducción al álgebra lineal utilizando la matriz de Sylvester.
Encontrar la coincidencia máxima.

A menudo, los algoritmos para esos problemas debían inventarse por separado y no podían adaptarse ingenuamente de algoritmos conocidos; la eliminación gaussiana y el algoritmo euclidiano se basan en operaciones realizadas en secuencia. Se podría contrastar un sumador de acarreo en cascada con un sumador de anticipación de acarreo .

Ejemplo

Un ejemplo de problema en NC ¹ es la verificación de paridad en una cadena de bits. ^{[ 6 ]} El problema consiste en contar el número de 1s en una cadena formada por 1 y 0. Una solución simple consiste en sumar todos los bits de la cadena. Dado que la suma es asociativa, $x_{1}+\cdots +x_{n}=\left(x_{1}+\cdots +x_{\frac {n}{2}}\right)+\left(x_{{\frac {n}{2}}+1}+\cdots +x_{n}\right).$ Aplicando recursivamente dicha propiedad, es posible construir un árbol binario de longitud $O(\log(n))$ en la que cada suma entre dos bits $x_{i}$ y $x_{j}$ se puede expresar mediante operadores lógicos básicos , por ejemplo, a través de la expresión booleana. $(x_{i}\land \neg x_{j})\lor (\neg x_{i}\land x_{j})$ .

La jerarquía de NC

NC ⁱ es la clase de problemas de decisión decidibles por circuitos booleanos uniformes con un número polinomial de compuertas de como máximo dos entradas y profundidad $O ((log n) i)$ , o la clase de problemas de decisión resolubles en tiempo O ((log n ) ⁱ ) en una computadora paralela con un número polinomial de procesadores. Claramente,

{\mathsf {NC}}^{0}\subseteq {\mathsf {NC}}^{1}\subseteq \cdots \subseteq {\mathsf {NC}}^{i}\subseteq \cdots \subseteq {\mathsf {NC}}

que conforma la jerarquía NC .

La clase más pequeña, NC ⁰ , es la clase de funciones definibles por circuitos booleanos con profundidad constante y fan-in limitado.

La siguiente clase más pequeña, NC ¹ , es igual a BW ₄⁰ , el conjunto de todos los problemas resolubles mediante circuitos de entrada acotados de tamaño polinomial y ancho 4 o menor. Esto es cierto tanto para el caso uniforme como para el no uniforme (basta con la uniformidad DLOGTIME). ^{[ 7 ]}^{: 142}

Se pueden relacionar las clases NC con las clases espaciales L , SL , ^{[ 7 ]}^{: 137}NL , ^{[ 8 ]} LOGCFL y AC . ^{[ 9 ]}

{\mathsf {NC}}^{1}\subseteq {\mathsf {L}}={\mathsf {SL}}\subseteq {\mathsf {NL}}\subseteq {\mathsf {LOGCFL}}\subseteq {\mathsf {AC}}^{1}\subseteq {\mathsf {NC}}^{2}.

Las clases NC están relacionadas con las clases AC, que se definen de manera similar, pero con compuertas que tienen un fan-in ilimitado. Para cada i , ^{[ 5 ]}^{[ 9 ]}^{[ 10 ]}

{\mathsf {NC}}^{i}\subseteq {\mathsf {AC}}^{i}\subseteq {\mathsf {AC}}^{i}[p]\subseteq {\mathsf {ACC}}^{i}\subseteq {\mathsf {TC}}^{i}\subseteq {\mathsf {NC}}^{i+1}

Como consecuencia inmediata de esto, NC = AC . ^{[ 11 ]}

También, ${\mathsf {NC}}^{0}\subsetneq {\mathsf {AC}}^{0}\subsetneq {\mathsf {ACC}}^{0}$ . ^{[ 5 ]}

De manera similar, NC es equivalente a los problemas resolubles en una máquina de Turing alternante restringida a como máximo dos opciones en cada paso con un espacio de O (log n ) y $(\log n)^{O(1)}$ alternancias. ^{[ 12 ]}

Es una cuestión abierta importante si ${\mathsf {TC}}^{0}\subsetneq {\mathsf {NC}}^{1}$ ( Vollmer 1998 , p. 126) . Un resultado parcial significativo establece que si existe algún $\epsilon >0$ y un problema en ${\mathsf {NC}}^{1}$ , de tal manera que requiere al menos $\Omega (n^{1+\epsilon })$ puertas en ${\mathsf {TC}}^{0}$ , entonces esto puede ser arrancado de manera que requiera puertas superpolinomiales y, por lo tanto, no en ${\mathsf {TC}}^{0}$ . ^{[ 13 ]}

Uniformidad

Se están considerando diversos niveles de uniformidad. Una familia de circuitos booleanos es uniforme si los esquemas de cualquier miembro de la familia pueden generarse mediante una máquina de Turing bajo diferentes restricciones de recursos. Con distintos niveles de restricciones, se obtendrían posiblemente distintas clases de complejidad, de modo que una restricción más estricta daría lugar a una clase de complejidad menor.

En la literatura, se han considerado las siguientes uniformidades para la clase NC ¹ , ordenadas según su resistencia: ^{[ 7 ]}^{: 139}^{[ 14 ]}

NC ¹ mismo. Esto también se llama el $U_{E^{*}}$ -uniformidad. Es equivalente a ALOGTIME .
ESPACIO DE REGISTRO .
PAG .
Computable . Se permite cualquier máquina de Turing que se detenga.
No uniforme . Este es el caso más fuerte. La familia de circuitos booleanos puede contener elementos arbitrarios del ancho y la profundidad correctos, incluso si la familia no puede ser generada por ningún algoritmo.

Por defecto, la literatura utiliza la uniformidad LOGSPACE .

Porque es posible que ${\mathsf {NC}}^{1}\subsetneq {\mathsf {LOGSPACE}}$ , los investigadores pueden usar la uniformidad NC ¹ , ya que es un posible fortalecimiento. Para evitar la autorreferencia, NC ¹ -uniforme NC ¹ se define de la siguiente manera: Una familia de circuitos booleanos NC ¹ es NC ¹ -uniforme si el conjunto de descripciones es decidido por una máquina de Turing alterna ALOGTIME . La máquina lee en una longitud- $n$ descripción de un circuito booleano y paradas en el tiempo $O(\log n)$ . ^{[ 7 ]}^{: 139}

Para las clases superiores NC ² , NC ³ , ..., se pueden definir uniformidades similares. Sin embargo, para $k\geq 2$ , NC ^k -uniform NC ^k y LOGSPACE -uniform NC ^k son iguales, y ambos son equivalentes a la siguiente definición: La familia es decidida por una máquina de Turing alternante . La máquina lee en una longitud- $n$ descripción de un circuito booleano y paradas en el tiempo $O((\log n)^{k})$ y espacio $O(\log n)$ . ^{[ 7 ]}^{: 139}

Problema abierto: ¿Es NC apropiado?

Problema sin resolver en informática

¿Es el?

{\mathsf {NC}}

¿Jerarquía propiamente dicha?

Más problemas sin resolver en informática

Una de las principales preguntas abiertas en la teoría de la complejidad es si toda contención en la jerarquía NC es propia o no. Papadimitriou observó que, si NC ⁱ = NC ^{i +1} para algún i , entonces NC ⁱ = NC ^j para todo j ≥ i , y como resultado, NC ⁱ = NC . Esta observación se conoce como colapso de la jerarquía NC porque incluso una sola igualdad en la cadena de contenciones

{\mathsf {NC}}^{1}\subseteq {\mathsf {NC}}^{2}\subseteq \cdots

implica que toda la jerarquía NC "colapsa" hasta algún nivel i . Por lo tanto, hay 2 posibilidades:

${\mathsf {NC}}^{1}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i+j}\subsetneq \cdots {\mathsf {NC}}$
${\mathsf {NC}}^{1}\subsetneq \cdots \subsetneq {\mathsf {NC}}^{i}=\cdots ={\mathsf {NC}}^{i+j}=\cdots {\mathsf {NC}}$

Existe la creencia generalizada de que (1) es el caso, aunque aún no se ha descubierto ninguna prueba sobre la veracidad de ninguna de las dos afirmaciones.

Si existe un problema que sea NC -completo bajo reducciones LOGSPACE o NC ¹ , entonces la jerarquía NC colapsa. ^{[ 7 ]}^{: 136}

Teorema de Barrington

Un programa de ramificación con n variables de ancho k y longitud m consta de una secuencia de m instrucciones. Cada instrucción es una tupla ( i , p , q ), donde i es el índice de la variable a comprobar (1 ≤ i ≤ n ), y p y q son funciones de {1, 2, ..., k } a {1, 2, ..., k }. Los números 1, 2, ..., k se denominan estados del programa de ramificación. El programa comienza inicialmente en el estado 1, y cada instrucción ( i , p , q ) cambia el estado de x a p ( x ) o q ( x ), dependiendo de si la i -ésima variable es 0 o 1. La función que asigna una entrada a un estado final del programa se denomina resultado del programa (más precisamente, el resultado de una entrada es la función que asigna cualquier estado inicial al estado final correspondiente). El programa acepta un conjunto $A\subseteq 2^{n}$ de valores variables cuando hay algún conjunto de funciones $F\subseteq k^{k}$ de tal manera que una secuencia variable $x\in 2^{n}$ está en A precisamente cuando su rendimiento está en F.

Una familia de programas ramificados consiste en un programa ramificado con n variables para cada n . Acepta un lenguaje cuando el programa de n variables acepta el lenguaje restringido a una longitud de n entradas.

Es fácil demostrar que todo lenguaje L en {0,1} puede ser reconocido por una familia de programas de ramificación de ancho 5 y longitud exponencial, o por una familia de ancho exponencial y longitud lineal.

Todo lenguaje regular en {0,1} puede ser reconocido por una familia de programas de ramificación de ancho constante y número lineal de instrucciones (ya que un autómata finito determinista puede convertirse en un programa de ramificación). BWBP denota la clase de lenguajes reconocibles por una familia de programas de ramificación de ancho acotado y longitud polinómica. ^{[ 15 ]}

El teorema de Barrington ^{[ 16 ]} dice que BWBP es exactamente no uniforme NC ¹ . La demostración utiliza la no solubilidad del grupo simétrico S ₅ . ^{[ 15 ]}

El teorema resulta bastante sorprendente. Por ejemplo, implica que la función de mayoría se puede calcular mediante una familia de programas de ramificación de ancho constante y tamaño polinomial, mientras que la intuición podría sugerir que para lograr un tamaño polinomial se necesita un número lineal de estados.

Demostración del teorema de Barrington

Un programa de ramificación de ancho constante y tamaño polinomial se puede convertir fácilmente (mediante divide y vencerás) en un circuito en NC ¹ .

Por el contrario, supongamos que se nos da un circuito en NC ^1. Sin pérdida de generalidad, supongamos que utiliza únicamente compuertas AND y NOT.

Lema 1 — Si existe un programa de ramificación que a veces funciona como una permutación P y a veces como una permutación Q , multiplicando por la derecha las permutaciones en la primera instrucción por α , y en la última instrucción multiplicando por la izquierda por β , podemos hacer un circuito de la misma longitud que se comporta como β P α o β Q α , respectivamente.

Se denomina programa de ramificación α-calculador a un circuito C si funciona como identidad cuando la salida de C es 0, y como α cuando la salida de C es 1.

Como consecuencia del Lema 1 y del hecho de que todos los ciclos de longitud 5 son conjugados , para cualesquiera dos ciclos de longitud 5 , α y β , si existe un programa de ramificación α-calcula un circuito C , entonces existe un programa de ramificación β-calcula el circuito C , de la misma longitud.

Lema 2 : existen 5 ciclos γ , δ tales que su conmutador $ε = γδγ -1 δ -1$ es un ciclo de 5. Por ejemplo, γ = (1 2 3 4 5), δ = (1 3 5 4 2) dando ε = (1 3 2 5 4).

Prueba

Ahora demostraremos el teorema de Barrington por inducción:

Supongamos que tenemos un circuito C que toma entradas x ₁ ,..., x _n y supongamos que para todos los subcircuitos D de C y 5 ciclos α, existe un programa de ramificación α-calcula D . Demostraremos que para todos los 5 ciclos α, existe un programa de ramificación α-calcula C .

Si el circuito C simplemente emite algún bit de entrada x _i , el programa de ramificación que necesitamos tiene solo una instrucción: comprobar el valor de x _i (0 o 1) y emitir la identidad o α (respectivamente).
Si el circuito C produce ¬ A para algún circuito A diferente , cree un programa de ramificación que α ⁻¹ -calcule A y luego multiplique la salida del programa por α. Por el Lema 1, obtenemos un programa de ramificación para A que produce la identidad o α, es decir, α -calcule ¬ A = C.
Si el circuito C produce A ∧ B para los circuitos A y B , unimos los programas de ramificación que γ -calculan A , δ -calculan B , γ ⁻¹ -calculan A y δ ⁻¹ -calculan B para una elección de 5-ciclos γ y δ tales que su conmutador $ε = γδγ -1 δ -1$ también es un 5-ciclo. (La existencia de tales elementos se estableció en el Lema 2.) Si uno o ambos circuitos producen 0, el programa resultante será la identidad debido a la cancelación; si ambos circuitos producen 1, el programa resultante producirá el conmutador ε . En otras palabras, obtenemos un programa que ε -calcula A ∧ B. Debido a que ε y α son dos 5-ciclos, son conjugados y, por lo tanto, existe un programa α -calculando A ∧ B por el Lema 1.

Al suponer que los subcircuitos tienen programas de ramificación de modo que sean α- computadores para todos los 5-ciclos $α \in S 5$ , hemos demostrado que C también tiene esta propiedad, como se requería.

El tamaño del programa de ramificación es como máximo 4d ^, donde d es la profundidad del circuito. Si el circuito tiene profundidad logarítmica, el programa de ramificación tiene longitud polinómica.

Notas

↑ Cook, SA (1981). "Hacia una teoría de la complejidad de la computación paralela síncrona" . L'Enseignement Mathématique . 27 : 99–124 . Archivado del original el 10 de marzo de 2022.
↑ Cook, Stephen A. (1985-01-01). "Una taxonomía de problemas con algoritmos paralelos rápidos" . Information and Control . Conferencia Internacional sobre Fundamentos de la Teoría de la Computación. 64 (1): 2– 22. doi : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .
↑ Pippenger, Nicholas (1979). "Sobre límites de recursos simultáneos" . XX Simposio Anual sobre Fundamentos de la Informática (SFCS 1979) . págs. 307–311 . doi : 10.1109/SFCS.1979.29 . ISSN 0272-5428 . S2CID 7029313 .
^ Arora y Barak (2009) p.120
^ Arora y Barak (2009 ) p.118
↑ David Mix Barrington; Alexis Maciel (18 de julio de 2000). "Conferencia 2: La complejidad de algunos problemas" (PDF) . Sesión de verano IAS/PCMI 2000 - Programa de pregrado en matemáticas Clay - Curso básico sobre complejidad computacional . Universidad de Clarkson . Consultado el 11 de noviembre de 2021 .
1 2 3 4 5 6 Leeuwen, J. van, ed. (1990). Manual de informática teórica . Ámsterdam ; Nueva York : Cambridge, Mass: Elsevier ; MIT Press. ISBN 978-0-444-88075-8.
^ Papadimitriou (1994) Teorema 16.1
1 2 Clote y Kranakis (2002) pág. 437
↑ "Complexity Zoo:T - Complexity Zoo" . complexityzoo.net . Consultado el 10 de marzo de 2025 .
↑ Clote y Kranakis (2002) pág. 12
↑ S. Bellantoni e I. Oitavem (2004). "Separando NC a lo largo del eje delta". Theoretical Computer Science . 318 ( 1–2 ): 57–78 . doi : 10.1016/j.tcs.2003.10.021 .
↑ Allender, Eric; Koucký, Michal (marzo de 2010). "Amplificación de límites inferiores mediante la autorreducibilidad" . Journal of the ACM . 57 (3): 1– 36. doi : 10.1145/1706591.1706594 . hdl : 11104/0192003 . ISSN 0004-5411 .
↑ Mix Barrington, David A.; Immerman, Neil; Straubing, Howard (1990-12-01). "Sobre la uniformidad dentro de NC1" . Journal of Computer and System Sciences . 41 (3): 274– 306. doi : 10.1016/0022-0000(90)90022-D . ISSN 0022-0000 .
1 2 Clote y Kranakis (2002) pág. 50
↑ Barrington, David A. (1989). "Los programas de ramificación de tamaño polinomial de ancho limitado reconocen exactamente esos lenguajes en NC ¹ " (PDF) . J. Comput. Syst. Sci . 38 (1): 150– 164. doi : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

Referencias

Arora, Sanjeev ; Barak, Boaz (2009). Complejidad computacional. Un enfoque moderno . Cambridge University Press . ISBN 978-0-521-42426-4. Zbl 1193.68112 .
Clote, Peter; Kranakis, Evangelos (2002). Funciones booleanas y modelos de computación . Textos en Informática Teórica. Una serie de EATCS. Berlín: Springer-Verlag . ISBN 3-540-59436-1. Zbl 1016.94046 .
Greenlaw, Raymond, James Hoover y Walter Ruzzo. Límites de la computación paralela; Teoría de la P-completitud . Archivado el 4 de junio de 2013 en Wayback Machine. ISBN 0-19-508591-4
Kozen, Dexter C. (1992). El diseño y análisis de algoritmos .Clases 28-34 y 36
Kozen, Dexter C. (2006). Teoría de la Computación . Textos en Informática. Springer-Verlag . ISBN 1-84628-297-7. Zbl 1102.68025 . Lección 12: Relación de NC con las clases espacio-temporales
Papadimitriou, Christos (1993). «Sección 15.3: La clase NC ». Complejidad computacional (1.ª ed.). Addison Wesley. pp. 375–381 . ISBN 0-201-53082-1.
Straubing, Howard (1994). Autómatas finitos, lógica formal y complejidad de circuitos . Avances en informática teórica. Basilea: Birkhäuser. ISBN 3-7643-3719-2. Zbl 0816.68086 .
Vollmer, Heribert (1998). Introducción a la complejidad de circuitos. Un enfoque uniforme . Textos en Informática Teórica. Berlín: Springer-Verlag . ISBN 3-540-64310-9. Zbl 0931.68055 .

[1] Cook, SA (1981). "Hacia una teoría de la complejidad de la computación paralela síncrona" . L'Enseignement Mathématique . 27 : 99–124 . Archivado del original el 10 de marzo de 2022.

[2] Cook, Stephen A. (1985-01-01). "Una taxonomía de problemas con algoritmos paralelos rápidos" . Information and Control . Conferencia Internacional sobre Fundamentos de la Teoría de la Computación. 64 (1): 2– 22. doi : 10.1016/S0019-9958(85)80041-3 . ISSN 0019-9958 .

[3] Pippenger, Nicholas (1979). "Sobre límites de recursos simultáneos" . XX Simposio Anual sobre Fundamentos de la Informática (SFCS 1979) . págs. 307–311 . doi : 10.1109/SFCS.1979.29 . ISSN 0272-5428 . S2CID 7029313 .

[AB120-4] Arora y Barak (2009) p.120

[AB118-5] Arora y Barak (2009 ) p.118

[6] David Mix Barrington; Alexis Maciel (18 de julio de 2000). "Conferencia 2: La complejidad de algunos problemas" (PDF) . Sesión de verano IAS/PCMI 2000 - Programa de pregrado en matemáticas Clay - Curso básico sobre complejidad computacional . Universidad de Clarkson . Consultado el 11 de noviembre de 2021 .

[:0-7] 1 2 3 4 5 6 Leeuwen, J. van, ed. (1990). Manual de informática teórica . Ámsterdam ; Nueva York : Cambridge, Mass: Elsevier ; MIT Press. ISBN 978-0-444-88075-8.

[8] Papadimitriou (1994) Teorema 16.1

[CK437-9] 1 2 Clote y Kranakis (2002) pág. 437

[10] "Complexity Zoo:T - Complexity Zoo" . complexityzoo.net . Consultado el 10 de marzo de 2025 .

[CK12-11] Clote y Kranakis (2002) pág. 12

[12] S. Bellantoni e I. Oitavem (2004). "Separando NC a lo largo del eje delta". Theoretical Computer Science . 318 ( 1–2 ): 57–78 . doi : 10.1016/j.tcs.2003.10.021 .

[13] Allender, Eric; Koucký, Michal (marzo de 2010). "Amplificación de límites inferiores mediante la autorreducibilidad" . Journal of the ACM . 57 (3): 1– 36. doi : 10.1145/1706591.1706594 . hdl : 11104/0192003 . ISSN 0004-5411 .

[14] Mix Barrington, David A.; Immerman, Neil; Straubing, Howard (1990-12-01). "Sobre la uniformidad dentro de NC1" . Journal of Computer and System Sciences . 41 (3): 274– 306. doi : 10.1016/0022-0000(90)90022-D . ISSN 0022-0000 .

[CK50-15] 1 2 Clote y Kranakis (2002) pág. 50

[Bar89-16] Barrington, David A. (1989). "Los programas de ramificación de tamaño polinomial de ancho limitado reconocen exactamente esos lenguajes en NC ¹ " (PDF) . J. Comput. Syst. Sci . 38 (1): 150– 164. doi : 10.1016/0022-0000(89)90037-8 . ISSN 0022-0000 . Zbl 0667.68059 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]