Научные интересы

Мои основные научные интересы концентрированы вокруг проблем анализа структур, связанных с относительной сложностью вычислений значений функций натурального аргумента. Главной мерой такой сложности является сводимость по Тьюрингу: f вычисляется проще, чем g, если существует машина Тьюринга, которая может вычислить значения f при условии, что она имеет доступ к значениям g. Кроме того, я интересовался также другими вариантами сложности вычислений, которые определяются наложением разного рода ограничений  на понятие «доступ к значениям g». Основными направлениями этих исследований являлись проблемы, связанные с разработкой структурных теорий возникающих моделей вычислений, а также оценка  информационной насыщенности различных естественных классов функций. Полученные в этом направлении результаты позволили сформулировать критерии принадлежности конкретных совокупностей  функций к тем или другим классам сложностей, а также выявить основные структурные различия между различными моделями вычислений.       

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

Избранные публикации:

1. Критерий полноты рекурсивно перечислимых множеств и некоторые обобщения теоремы о неподвижной точке, Известия вузов, Матем., 1977, №4, с. 3-9.

2. О некоторых обобщениях теоремы о неподвижной точке, Известия вузов, Матем., 1981,  №5, с. 9-18. 

3. Структурные свойства степеней ниже 0’, ДАН СССР, 1985, т.283, №2,  с. 270-273.

4. Рекурсивно перечислимые множества и степени неразрешимости, Казань, изд-во КГУ, 1986. 312 c.

 5. Полнота в арифметической иерархии и неподвижные точки, Алгебра и логика, 1989,  т. 28, №1,   с. 3-17.

 6. Interpolating  d-r.e. and REA degrees between r.e. degrees, Annals of Pure and Applied Logic, v.78, 1996, p. 29-56. (with Lempp S., Shore R.A.)

 7. Degree structures in the local degree theory, Lecture Notes in Pure and Applied Math., 1997, vol.187, p. 49-74.

 8. Relative enumerability in the difference hierarchy, Journal of Symbolic Logic, 1998, v. 63,  p. 411-420. (with LaForte G, Slaman T.)

 9. Open questions about the n-c.e. degrees, Contemporary Mathematics, v. 257, 2000, p. 15-22 .

 10. Таблично-полные множества и Колмогоровская сложность вычислений, Юбилейный сборник избранных трудов членов АН РТ, Казань: Фолиант, 2002, с. 199-209.

 11. Truth-table complete computably enumerable sets, "Computability and models", S.B. Cooper and S.S. Goncharov, editors, 2003, c. 1-10.

 12. Generalized Tabular Reducibilities in Infinite Levels of Ershov Difference Hierarchy,  Lecture Notes in Computer Science, v. 88, 2006, p. 15-23.

 13. Definability and Elementary Equivalence in the Ershov Difference Hierarchy, Lecture Notes in Logic, v. 32, 2009, p. 1-17 

 14. Иерархия Ершова,  Казань, из-во КГУ, 2007,  86 с.

 15. Total degrees and nonsplitting properties of Sigma-2-0-enumeration degrees, Lect. Notes in Computer Science, v. 4978, 2008, p. 589-596 (with Cooper S.B., Kalimullin I.Sh., Soskova M.)

 16. The Ershov hierarchy. In: Computability in Context. Computation and Logic in the Real World (S.B. Cooper, A.Sorbi, eds.) Imperial College Press, London, 2011, p. 49-100.

 17. On Downey’s conjecture, Journal of Symbolic Logic., 2010, v. 75, p. 401 – 441 (with Kalimullin I.Sh., Lempp S.)

 18. Model-theoretic properties of the n-c.e. degrees, Journal of Logic Computation. - v. 22, 2012, p.212-231 

 19. Definable relations in Turing degree structures, Journal of Logic Computation, v. 23, 2013, p. 1145-1154 

 20. Структурная теория степеней неразрешимости: достижения и открытые проблемы//Алгебра и логика. - 2015. - т.54. -№4. c. 529-535.