Гипотеза Аандераа — Карпа — Розенберга (Inhkmy[g Ggu;yjgg — Tgjhg — Jk[yuQyjig)

Нерешённые проблемы информатики: Доказать или опровергнуть гипотезу Аандераа — Карпа — Розенберга.

Гипотеза Аандераа — Карпа — Розенберга (известная также как гипотеза Аандераа — Розенберга или гипотеза трудности) — это группа связанных гипотез о числе вопросов в форме «Имеется ли ребро между вершиной u и вершиной v?», на которые следует ответить, чтобы определить, обладает или нет неориентированный граф определённым свойством (инвариантом), таким как планарность или двудольность. Гипотеза названа именами норвежского математика Стола Аандераа и американских учёных Ричарда М. Карпа и Арнольда Л. Розенберга. Согласно гипотезе, для широкого класса инвариантов никакой алгоритм не может гарантировать, что алгоритм может опустить какой-либо запрос — любой алгоритм определения, обладает ли граф свойством, неважно, насколько умён этот алгоритм, он должен проверить каждую пару вершин, прежде чем дать ответ. Свойство, удовлетворяющее гипотезе, называется трудным^[англ.].

Более точно, гипотеза Аандераа — Розенберга утверждает, что любой детерминированный алгоритм должен проверить по меньшей мере фиксированную долю всех возможных пар вершин, чтобы определить в худшем случае^[англ.] любое нетривиальное монотонное свойство графа. В этом контексте свойство монотонно, если оно остаётся верным при добавлении рёбер (так что свойство планарности монотонным не является, а вот непланарность монотонна). Более строгая версия этой гипотезы, называемая гипотезой трудности или гипотезой Аандераа — Карпа — Розенберга, утверждает, что необходимо в точности ${\tfrac {n(n-1)}{2}}$ проверок. Были сформулированы и изучались версии проблемы для вероятностных и квантовых алгоритмов.

Детерминированную гипотезу Аандераа — Розенберга доказали Ривест и Виллемин^[1], но более сильная гипотеза гипотеза Аандераа — Карпа — Розенберга остаётся недоказанной. Кроме того, существует большая разница между нижней границей и лучшей доказанной нижней границей для вероятностной и квантовой сложности по количеству запросов.

Пример

Свойство не быть пустым (то есть иметь по меньшей мере одно ребро) монотонно, поскольку добавление другого ребра к непустому графу даёт непустой граф. Существует простой алгоритм тестирования, является ли граф не пустым — цикл через все пары вершин и проверка, связана ли каждая пара ребром. Если ребро найдено таким способом, прерываем цикл и рапортуем, что граф не пустой, а если цикл завершается без нахождения какого-либо ребра, то рапортуем, что граф пустой. На таких графах (например, полных графах) этот алгоритм быстро завершается без проверки каждой пары вершин, но на пустом графе алгоритм проверяет все возможные пары, перед тем как завершиться. Поэтому сложность алгоритма по запросам равна ${\tfrac {n(n-1)}{2}}$ — в худшем случае алгоритм делает ${\tfrac {n(n-1)}{2}}$ проверок.

Описанный выше алгоритм не является единственным возможным методом проверки непустоты, но из гипотезы Аандераа — Карпа — Розенберга вытекает, что любой детерминантный алгоритм для проверки непустоты имеет ту же сложность по запросам ${\tfrac {n(n-1)}{2}}$ . То есть свойство быть непустым является трудным. Для этого свойства результат просто проверить прямо — если алгоритм не выполнит ${\tfrac {n(n-1)}{2}}$ проверок, он не сможет отличить пустой граф от графа, содержащего одно ребро непроверенной пары вершин и должен дать неверный ответ для одного из двух этих графов (либо для пустого, либо для графа с ребром).

Определения

В контексте этой статьи все графы будут простыми и неориентированными, если не утверждается иное. Это означает, что рёбра графа образуют множество (но не мультимножество) и концами каждого ребра является пара различных вершин. Предполагается, что графы имеют неявное представление^[англ.], в котором каждая вершина имеет уникальный идентификатор или метку и в котором можно проверить смежность двух вершин, но в графе для проверки смежности можно осуществлять только базовые операции.

Неформально, свойство графа (или инвариант графа, оба термина в данной статье используются как синонимы) — это свойство графа, которое не зависит от разметки. Более формально, свойство графа — это отображение из множества всех графов в {0,1} так, что изоморфные графы отображаются в одно и то же значение. Например, свойство содержать по меньшей мере одну вершину степени 2 является инвариантом графа, но свойство, что первая вершина имеет степень 2, инвариантом графа не является, поскольку свойство зависит от разметки графа (в частности, оно зависит от того, какая вершина считается «первой»). Инвариант графа называется нетривиальным, если он не имеет одно и то же значение для всех графов. Например, свойство быть графом является тривиальным свойством, поскольку все графы этим свойством обладают. Но с другой стороны, свойство быть пустым нетривиально, поскольку пустой граф обладает данным свойством, а непустой не обладает. Говорят, что свойство графа монотонно, если добавление рёбер не разрушает свойства. Альтернативно, если граф обладает монотонным свойством, тогда любой суперграф этого графа на том же наборе вершин тоже обладает этим свойством. Например, свойство быть непланарным монотонно — суперграф непланарного графа также непланарен. Однако свойство быть регулярным не монотонно.

Для сложности запросов часто используется нотация «O» большое. Кратко, f(n) есть $O(g(n))$ , если для любого достаточно большого $nf(n)\leqslant cg(n)$ для некоторой положительной константы c. Аналогично, f(n) есть $\Omega (g(n))$ , если для достаточно больших $nf(n)\geqslant cg(n)$ для некоторой положительной константы c. Наконец, f(n) есть $\Theta (g(n))$ , если она есть как $O(g(n))$ , так и $\Omega (g(n))$ .

Сложность запроса

Сложность детерминированного запроса вычисления функции от n бит $(x_{1},x_{2},\dots ,x_{n})$ равна числу бит x_i, которые должен прочитать детерминированный алгоритм в худшем случае для определения значения функции. Например, если функция принимает значение 0, если все биты равны 0 и значение 1 в противном случае (то есть функция OR), то сложность детерминированных запросов в точности равна n. В худшем случае первые n − 1 прочитанных бит будут равны 0 и значение функции будет зависеть только от последнего бита. Если алгоритм не прочитает этот бит, он может дать неверный ответ. Число прочитанных бит называется также числом запросов, сделанных на входе. Можно представить так, что алгоритм спрашивает (осуществляет запрос) вход о конкретном бите и вход отвечает на этот запрос.

Сложность вероятностного запроса выполнения функции определяется аналогично, за исключением того, что алгоритм может быть вероятностным, то есть он может подбрасывать монету и использовать выпавшее значение стороны монеты для решения, какой бит запрашивать. Однако вероятностный алгоритм должен продолжать давать верные ответы на все входные запросы — ошибки недопустимы. Такие алгоритмы называются алгоритмами Лас-Вегаса и их следует отличать от алгоритмов Монте-Карло, в которых некоторые ошибки допустимы. Сложность вероятностного запроса может быть определена в смысле Монте-Карло, но гипотеза Аандераа — Карпа — Розенберга говорит о сложности запросов для инвариантов графа в смысле Лас-Вегаса.

Квантовая сложность запросов является естественным обобщением сложности вероятностного запроса, естественно, с разрешением квантовых запросов и ответов. Квантовая сложность запросов может быть также определена в смысле алгоритмов Монте-Карло или алгоритмов Лас-Вегаса, но обычно имеются в виду квантовые алгоритмы Монте-Карло.

В контексте этой гипотезы вычисляемая функция является свойством графа, а входом является строка размера ${\tfrac {n(n-1)}{2}}$ , которая задаёт местоположение рёбер на графе с n вершинами, поскольку граф может иметь максимум ${\tfrac {n(n-1)}{2}}$ рёбер. Сложность запроса любой функции ограничена сверху значением ${\tfrac {n(n-1)}{2}}$ , поскольку весь вход будет прочитан после ${\tfrac {n(n-1)}{2}}$ запросов, что и определяет полностью входной граф.

Сложность детерминированных запросов

Для детерминированных алгоритмов Розенберг^[2] предположил, что для всех нетривиальных свойств графов на n вершинах решение, обладает ли граф этим свойством, требует $\Omega (n^{2})$ запросов. Ясно, что требуется нетривиальность условия, поскольку существуют тривиальные свойства типа «это граф?», на которые можно ответить без всякого запроса вообще.

Гипотезу опроверг Аандераа, который предложил свойство ориентированного графа (свойство иметь «сток»), проверка которого требует всего O(n) запросов. Сток в ориентированном графе — это вершина, имеющая входящую полустепень n-1 и исходящую полустепень 0^[3]. Это свойство может быть проверено за менее чем 3n запросов^[4]. Свойство неориентированного графа, которое может быть проверено за O(n) запросов, это свойство «граф является графом-скорпионом», впервые описанное в статье Беста, ван Эмде Боаза и Ленстры^[4]. Граф «скорпион» — это граф, содержащий путь, состоящий из трёх вершин, такой, что одна конечная вершина пути соединена со всеми остальными вершинами графа, в то время как две оставшиеся вершины пути соединены только с вершинами самого пути.

Тогда Аандераа и Розенберг сформулировали новую гипотезу (гипотезу Аандераа — Розенберга), которая утверждает, что решение, обладает ли граф нетривиальным монотонным свойством, требует $\Omega (n^{2})$ запросов^[5]. Эту гипотезу решили Райвест и Вюйемен^[1], показав, что нужно по меньшей мере ${\tfrac {n^{2}}{16}}$ запросов для проверки любого нетривиального монотонного свойства. Границу позже улучшили до ${\tfrac {n^{2}}{9}}$ Клейтман и Квятковски^[6], затем до ${\tfrac {n^{2}}{4}}-o(n^{2})$ Кан, Сакс и Стертевант^[7], до ${\tfrac {8}{25}}n^{2}-o(n^{2})$ Корнефель и Триш^[8] и до ${\tfrac {n^{2}}{3}}-o(n^{2})$ Шайдервайлер и Триш^[9].

Ричард Карп высказал более строгое утверждение (которое называется теперь гипотезой о трудности или гипотезой Аандераа–Карпа–Розенберга), что «любое нетривиальное монотонное свойство графов на n вершинах трудное» ^[10]. Свойство называется трудным, если определение, обладает ли граф данным свойством, требует ${\tfrac {n(n-1)}{2}}$ запросов^[11]. Эта гипотеза утверждает, что лучший алгоритм тестирования любого нетривиального монотонного свойства должно (в худшем случае) запросить все возможные рёбра. Эта гипотеза остаётся открытой, хотя было показано, что некоторые специальные свойства графов являются трудным для всех n. Гипотеза была решена для случая, когда n является степенью простого числа Каном, Саксом и Стертевантом^[7] с помощью топологического подхода. Гипотезу решил для всех нетривиальных монотонных свойств двудольных графов Яо^[12]. Было также доказано, что замкнутые относительно миноров свойства также трудны для больших n^[13].

Сложность вероятностного запроса

Ричард Карп также высказал гипотезу, что $\Omega (n^{2})$ запросов требуется для проверки нетривиальных свойств монотонности, даже если вероятностные алгоритмы разрешены. Никакого нетривиального свойства не известно, которое требует менее ${\tfrac {n^{2}}{4}}$ запросов для проверки. Линейная нижняя граница (то есть $\Omega (n))$ для всех монотонных свойств следует из очень общей связи между вероятностными и детерминированными сложностями запросов^[англ.]. Первую суперлинейную нижнюю для всех монотонных инвариантов дал Яо^[14], показавший, что требуется $\Omega (n\log ^{\tfrac {1}{12}}n)$ запросов. Её затем улучшил Кинг^[15] до $\Omega (n^{\tfrac {5}{4}})$ , а затем Хайналь^[16] до $\Omega (n^{\tfrac {4}{3}})$ . Этот результат затем улучшили до текущего хорошо известного значения границы $\Omega (n^{\tfrac {4}{3}}\log ^{\tfrac {1}{3}}n)$ Чакрабарти и Хот^[17].

Некоторые последние результаты дают нижние границы, которые определяются критической вероятностью p монотонного свойства рассматриваемого графа. Критическая вероятность p определяется как единственное p, такое, что случайный граф G(n, p) обладает этим свойством с вероятностью 1/2. Случайный граф G(n, p) — это граф с n вершинами, в котором каждое ребро присутствует с вероятностью p и наличие/отсутствие ребра не зависит от всех остальных рёбер. Фридгуд, Кан и Вигдерсон^[18] показали, что любой монотонный инвариант графа с критической вероятностью p требует $\Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)$ запросов. Для той же проблемы О'Доннелл, Сакс, Шрамм и Серведио^[19] показали нижнуюю границу $\Omega ({\frac {n^{\tfrac {4}{3}}}{p^{\tfrac {1}{3}}}})$ .

Как в детерминированном случае, есть много специальных инвариантов, для которых нижняя граница $\Omega (n^{2})$ известна. Более того, известны лучшие границы для некоторых классов инвариантов графов. Например, для проверки, имеет ли граф подграф, изоморфный какому-нибудь заданному графу (так называемая задача поиска изоморфного подграфа), лучшей известной нижней границей, согласно Грёгеру, является $\Omega (n^{\tfrac {3}{2}})$ ^[20].

Квантовая сложность запросов

Для равномерно ограниченной ошибки квантовой сложности запросов^[англ.] наилучшая известная нижняя граница равна $\Omega (n^{\tfrac {2}{3}}\log ^{\tfrac {1}{6}}n)$ , как заметил Эндрю Яо (результат не опубликован, но упомянут в статье^[21]). Граница получена комбинированием вероятностной нижней границы с квантовым состязательным методом (англ. quantum adversary method). Наилучшая нижняя граница, которую надеются достичь, равна $\Omega (n)$ , в отличие о классического случая, ввиду алгоритма Гровера, который даёт алгоритм с O(n) запросами для проверки монотонного свойства непустоты. Аналогично детерминированному и вероятностному случаям, есть некоторые свойства, которые, как известно, имеют нижнюю границу $\Omega (n)$ , например непустота (что следует из оптимальности алгоритма Гровера) и свойство содержать треугольник. Есть некоторые инварианты графа, для которых известно, что они имеют нижнюю границу $\Omega (n^{\tfrac {3}{2}})$ , и даже есть свойства с нижней границей $\Omega (n^{2})$ . Например, монотонное свойство непланарности требует $\Theta (n{\tfrac {3}{2}})$ запросов^[22], а монотонное свойства содержать более половины возможных рёбер (которое называется также мажоритарной функцией) требует $\Theta (n^{2})$ запросов^[23].

Примечания

↑ ¹ ² Rivest, Vuillemin, 1975.
↑ Rosenberg, 1973.
↑ Данное определение стока отличается от обычного определения стока. В данном определении предполагается, что все дуги графа входят в одну вершину (сток), а в обычном определении всего лишь предполагается, что из стока нет исходящих дуг (см. «Типы вершин графа»).
↑ ¹ ² Best, van Emde Boas, Lenstra, 1974.
↑ Triesch, 1996.
↑ Kleitman, Kwiatkowski, 1980.
↑ ¹ ² Kahn, Saks, Sturtevant, 1983.
↑ Korneffel, Triesch, 2010.
↑ Scheidweiler, Triesch, 2013.
↑ Lutz, 2001.
↑ Kozlov, 2008, с. 226-228.
↑ Yao, 1988.
↑ Chakrabarti, Khot, Shi, 2001.
↑ Yao, 1991.
↑ King, 1988.
↑ Hajnal, 1991.
↑ Chakrabarti, Khot, 2001.
↑ Friedgut, Kahn, Wigderson, 2002.
↑ O'Donnell, Saks, Schramm, Servedio, 2005.
↑ Gröger, 1992.
↑ Magniez, Santha, Szegedy, 2005.
↑ Ambainis, Iwama, Nakanishi, Nishimura и др., 2008.
↑ Beals, Buhrman, Cleve, Mosca, de Wolf, 2001.

Литература

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Quantum query complexity of Boolean functions with small on-sets // Proceedings of the 19th International Symposium on Algorithms and Computation. — Gold Coast, Australia: Springer-Verlag, 2008. — Т. 5369. — С. 907–918. — (Lecture Notes in Computer Science). — ISBN 978-3-540-92181-3. — doi:10.1007/978-3-540-92182-0_79..
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf. Quantum lower bounds by polynomials // Journal of the ACM. — 2001. — Т. 48, вып. 4. — С. 778–797. — doi:10.1145/502090.502097. — arXiv:quant-ph/9802049..
Best M.R, van Emde Boas P., Lenstra H.W. A sharpened version of the Aanderaa-Rosenberg conjecture. — Mathematisch Centrum Amsterdam, 1974. — (Report ZW 30/74).
Amit Chakrabarti, Subhash Khot. Improved Lower Bounds on the Randomized Complexity of Graph Properties // Proceedings of the 28th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 2001. — Т. 2076. — С. 285–296. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42287-7. — doi:10.1007/3-540-48224-5_24..
Amit Chakrabarti, Subhash Khot, Yaoyun Shi. Evasiveness of subgraph containment and related properties // SIAM Journal on Computing. — 2001. — Т. 31, вып. 3. — С. 866–875. — doi:10.1137/S0097539700382005..
Ehud Friedgut, Jeff Kahn, Avi Wigderson. Computing Graph Properties by Randomized Subcube Partitions // Randomization and Approximation Techniques in Computer Science. — Springer-Verlag, 2002. — Т. 2483. — С. 953. — (Lecture Notes in Computer Science). — ISBN 978-3-540-44147-2. — doi:10.1007/3-540-45726-7_9..
Hans Dietmar Gröger. On the randomized complexity of monotone graph properties // Acta Cybernetica. — 1992. — Т. 10, вып. 3. — С. 119–127. Архивировано 24 сентября 2015 года..
Péter Hajnal. An Ω(n^4/3) lower bound on the randomized complexity of graph properties // Combinatorica. — 1991. — Т. 11, вып. 2. — С. 131–143. — doi:10.1007/BF01206357..
Jeff Kahn, Michael Saks, Dean Sturtevant. A topological approach to evasiveness // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium on Foundations of Computer Science. — Los Alamitos, CA, USA: IEEE Computer Society, 1983. — С. 31–33. — ISBN 0-8186-0508-1. — doi:10.1109/SFCS.1983.4..
Valerie King. Lower bounds on the complexity of graph properties // Proc. 20th ACM Symposium on Theory of Computing. — Chicago, Illinois, United States, 1988. — С. 468–476. — ISBN 0-89791-264-0. — doi:10.1145/62212.62258..
Kleitman D.J., Kwiatkowski D.J. Further results on the Aanderaa-Rosenberg conjecture // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28. — С. 85–95. — doi:10.1016/0095-8956(80)90057-X.
Dmitry Kozlov. Combinatorial Algebraic Topology. — Springer-Verlag, 2008. — ISBN 978-3-540-73051-4.
Frank H. Lutz. Some results related to the evasiveness conjecture // Journal of Combinatorial Theory, Series B. — 2001. — Т. 81, вып. 1. — С. 110–124. — doi:10.1006/jctb.2000.2000.
Torsten Korneffel, Eberhard Triesch. An asymptotic bound for the complexity of monotone graph properties // Combinatorica. — Springer-Verlag, 2010. — Т. 30, вып. 6. — С. 735–743. — ISSN 0209-9683. — doi:10.1007/s00493-010-2485-3.
Frédéric Magniez, Miklos Santha, Mario Szegedy. Quantum algorithms for the triangle problem // Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. — Vancouver, British Columbia: Society for Industrial and Applied Mathematics, 2005. — С. 1109–1117..
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Every decision tree has an influential variable // Proc 46th IEEE Symposium on Foundations of Computer Science. — 2005. — С. 31–39. — ISBN 0-7695-2468-0. — doi:10.1109/SFCS.2005.34.
Ronald L. Rivest, Jean Vuillemin. A generalization and proof of the Aanderaa-Rosenberg conjecture // Proc. 7th ACM Symposium on Theory of Computing. — Albuquerque, New Mexico, United States, 1975. — С. 6–11. — doi:10.1145/800116.803747..
Arnold L. Rosenberg. On the time required to recognize properties of graphs: a problem // SIGACT News. — 1973. — Т. 5, вып. 4. — С. 15–16. — doi:10.1145/1008299.1008302..
Robert Scheidweiler, Eberhard Triesch. A Lower Bound for the Complexity of Monotone Graph Properties // SIAM Journal on Discrete Mathematics. — 2013. — Т. 27, № 1. — С. 257–265. — doi:10.1137/120888703.
Eberhard Triesch. On the recognition complexity of some graph properties // Combinatorica. — 1996. — Т. 16, вып. 2. — С. 259–268. — doi:10.1007/BF01844851..
Andrew Chi-Chih Yao. Monotone bipartite graph properties are evasive // SIAM Journal on Computing. — 1988. — Т. 17, вып. 3. — С. 517–520. — doi:10.1137/0217031..
Andrew Chi-Chih Yao. Lower bounds to randomized algorithms for graph properties // Journal of Computer and System Sciences. — 1991. — Т. 42, вып. 3. — С. 267–287. — doi:10.1016/0022-0000(91)90003-N..

Литература для дальнейшего чтения

Béla Bollobás. Chapter VIII. Complexity and packing // Extremal Graph Theory. — New York: Dover Publications, 2004. — С. 401–437. — ISBN 978-0-486-43596-1.
László Lovász; Young, Neal E. "Lecture Notes on Evasiveness of Graph Properties". arXiv:cs/0205031v1. {{cite arXiv}}: Неизвестный параметр |год= игнорируется (справка)
Catherine E Chronaki. A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions. — 1990.
Michael Saks. Decision Trees: Problems and Results, Old and New (неопр.). Дата обращения: 17 февраля 2019. Архивировано 3 марта 2016 года.

[_eeab9d4acf9b2f11-1] ¹ ² Rivest, Vuillemin, 1975.

[_56fb88d6ab458b5e-2] Rosenberg, 1973.

[3] Данное определение стока отличается от обычного определения стока. В данном определении предполагается, что все дуги графа входят в одну вершину (сток), а в обычном определении всего лишь предполагается, что из стока нет исходящих дуг (см. «Типы вершин графа»).

[_6ee1d651b2b024c2-4] ¹ ² Best, van Emde Boas, Lenstra, 1974.

[_955709b347c2a0f6-5] Triesch, 1996.

[_77e91d39c2da87a2-6] Kleitman, Kwiatkowski, 1980.

[_68ce642735fbc174-7] ¹ ² Kahn, Saks, Sturtevant, 1983.

[_9bce84b020f4d4a6-8] Korneffel, Triesch, 2010.

[_f7064c1216040ba5-9] Scheidweiler, Triesch, 2013.

[_104e2b1e0f47b467-10] Lutz, 2001.

[_6c4da920a161670f-11] Kozlov, 2008, с. 226-228.

[_2e5ee23c301ac982-12] Yao, 1988.

[_b4f3800d194e965c-13] Chakrabarti, Khot, Shi, 2001.

[_14d6517664ef5e0c-14] Yao, 1991.

[_31e34eb7c0652b58-15] King, 1988.

[_395a5b16c60ac27b-16] Hajnal, 1991.

[_2bf4d3f4b6ae5ce0-17] Chakrabarti, Khot, 2001.

[_d79175954c70ddaf-18] Friedgut, Kahn, Wigderson, 2002.

[_dc7214fcb78ade96-19] O'Donnell, Saks, Schramm, Servedio, 2005.

[_08e29aabe168d976-20] Gröger, 1992.

[_d23b12b303473f05-21] Magniez, Santha, Szegedy, 2005.

[_eab525b884ef4ea1-22] Ambainis, Iwama, Nakanishi, Nishimura и др., 2008.

[_2176f7de61361b1b-23] Beals, Buhrman, Cleve, Mosca, de Wolf, 2001.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]