Специальность ВАК:
01.01.06 (математическая логика, алгебра и теория чисел)
E-mail: Сайт: https://logic.pdmi.ras.ru/~hirsch Ключевые слова: теория сложности вычислений,
пропозициональная логика,
системы доказательств.
Основные темы научной работы:
Верхние оценки для задачи пропозициональной выполнимости и нижние оценки времени работы некоторых алгоритмов для этй задачи. Верхние и нижние оценки для полуалгебраических систем доказательств. Оптимальные эвристические алгоритмы.
Основные публикации:
E. A. Hirsch, D. Itsykson, I. Monakhov, A. Smal. On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography // Theory of Computing Systems 51(2):179-195. Springer, 2012.
E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning. A Deterministic $(2-2/(k+1))^n$ Algorithm for k-SAT Based on Local Search. Theoretical Computer Science, Elsevier, 289/1, 2002, pp. 69-83.
E. A. Hirsch. New Worst-Case Upper Bounds for SAT // Journal of Automated Reasoning, 24(4), Kluwer Academic Publishers, 2000, 397–420.
D. Grigoriev, E. A. Hirsch, D. V. Pasechnik. Complexity of Semi-Algebraic Proofs // Moscow Mathematical Journal 2(4): 647-679, 2002.
E. Dantsin, E. A. Hirsch. Worst-Case Upper Bounds // In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications. Vol. 185. IOS Press, 2009, pp.403-424.
