Схемная сложность

Схемная сложность

Как доказать, что для данной вычислительной задачи не существует эффективного алгоритма? Другими словами, как доказать нижнюю оценку на вычислительную сложность задачи? В разных моделях вычислений (машина Тьюринга, РАМ и пр.) сложность может несколько различаться. Очень простой и точной моделью вычислений являются булевы схемы. Схема соответствует очень просто устроенной программе и естественным образом реализуется в виде микросхемы: каждая инструкция такой программы — это применение бинарной булевой операции к результатам предыдущих операций или входным битам. Больше всего нам хотелось бы доказать, что для какой-нибудь NP-полной задачи не существует такой программы полиномиального размера. Это доказало бы, что классы P и NP не равны, то есть ответило бы на главный открытый вопрос computer science. На данный момент доказывать этого мы, конечно же, не умеем. Если не вводить никаких ограничений на тип схемы, мы умеем доказывать лишь слабые линейные нижние оценки. По этой причине активно изучаются различные ограниченные модели вычислений: например, формулы (они соответствуют программам, в которых результат каждой инструкции можно использовать в дальнейшем не более одного раза; такие программы действительно можно развернуть в однострочную формулу) или схемы константной глубины (то есть программы, которые хорошо распараллеливаются). Для таких моделей уже известны более сильные нижние оценки. Для получения таких оценок было разработано множество математически красивых методов.

Более того, недавние результаты Р. Вильямса устанавливают интересную связь между доказательством нижних оценок на сложность схем из некоторого класса и доказательством верхних оценок на время работы алгоритмов, проверяющих выполнимость схем из этого класса. Интуитивно кажется, что доказать верхнюю оценку для вычислительной задаче потенциально проще, чем нижнюю. Для доказательства верхней достаточно предъявить алгоритм и доказать верхнюю оценку на время его работы. В то же время для доказательства нижней оценки надо доказать, что вообще никакой алгоритм не может решить данную задачу быстро. Для этого, в частности, у всех быстрых алгоритмов нужно найти какое-то общее свойство, которое не позволяет им быстро решать данную задачу. Оказывается, однако, что данные две задачи удивительным образом оказываются связанными: построив эффективный алгоритм для некоторой задачи, можно автоматически доказать отсутствие быстрых алгоритмов для другой задачи!

 

Сотрудники кафедры: 

Э.А.ГиршА.А.КнопА.С.Куликов, А.В.Смаль

 

Публикации сотрудников кафедры

  1. Alexander Knop, Circuit Lower Bounds for Average-Case MA. Proceedings of CSR 2015.
  2. Magnus Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov. A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function. Proceedings of 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). IEEE Computer Society, pp. 89–98, 2016.
  3. Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov. On the Limits of Gate Elimination. Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). LIPIcs 58, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 46:1–46:13, 2016.
  4. Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki. Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). LIPIcs 58, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pp. 45:1–45:16, 2016.
  5. Alexander Golovnev, Alexander S. Kulikov. Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. Proceedings of 7th Innovations in Theoretical Computer Science (ITCS 2016). ACM, pp. 405-411, 2016.
  6. Evgeny Demenkov, Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin. New Lower Bounds on Circuit Size of Multi-output Functions. Theory of Computing Systems, Volume 56, Issue 4, pp 630-642. 2015.
  7. A.P. Davydow, S.I. Nikolenko. Circuit Complexity of Linear Functions: Gate Elimination and Feeble Security. Journal of Mathematical Sciences, vol. 188, no. 1, 2013, pp. 35–43.
  8. E.A. Hirsch, S.I. Nikolenko. Feebly Secure Cryptographic Primitives. Journal of Mathematical Sciences, vol. 188, no. 1, 2013, pp. 17–34.
  9. S.I. Nikolenko. Provably Secure Cryptographic Constructions. Cryptography and Security in Computing, InTech, 2012, pp. 3–22.
  10. Alexander S. Kulikov, Olga Melanich, Ivan Mihajlin. A 5n-o(n) Lower Bound on the Circuit Size over U_2 of a Linear Boolean Function. Proceedings of Computability in Europe (CiE 2012), Lecture Notes in Computer Science 7318, Springer, pp. 432–439, 2012.
  11. Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi. Computing All MOD-functions Simultaneously. Proceedings of 7th International Computer Science Symposium in Russia (CSR 2012), Lecture Notes in Computer Science 7353, Springer, pp. 81–88, 2012.
  12. Evgeny Demenkov, Alexander S. Kulikov. An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers. Proceedings of 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), Lecture Notes in Computer Science 6907, Springer, pp. 256–265, 2011.
  13. Arist Kojevnikov, Alexander S. Kulikov. Circuit Complexity and Multiplicative Complexity of Boolean Functions. Proceedings of Computability in Europe (CiE 2010), Lecture Notes in Computer Science 6158, pp. 239–245, 2010.
  14. Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlak. On Convex Complexity Measures. Theoretical Computer Science 411, Elsevier, pp. 1842-1854, 2010.
  15. Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev. New Upper Bounds on the Boolean Circuit Complexity of Symmetric Functions. Information Processing Letters 110(7), pp. 264-267, 2010.
  16. Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev. Finding Efficient Circuits Using SAT-solvers. Proceedings of the Twelfth International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), Lecture Notes in Computer Science 5584, Springer, pp. 32-44, 2009.
  17. E.A. Hirsch, S.I. Nikolenko. A feebly secure trapdoor function. Proceedings of the 4th Computer Science Symposium in Russia (CSR 2009), Lecture Notes in Computer Science, vol. 5675, 2009, pp. 129–142.

Квалификационные работы

  1. Г. Н. Ярославцев. Нахождение эффективных булевых схем при помощи SAT-солверов. Магистерская диссертация. СПбАУ РАН, 2010.
  2. Д. С. Тугарев. Нижние оценки на схемную сложность некоторых элементарных функций. Магистерская диссертация. СПбАУ РАН, 2013.
  3. Е. А. Деменков. Верхние и нижние оценки на схемную сложность явно заданных булевых функций. Диссертация на соискание учёной степени кандидата физико-математических наук. СПбГУ, 2013.