Нигматуллин Рошаль Габдулхаевич

5 декабря 1939 г., Казань – 19 декабря 1986 г., там же.

По окончании в 1962 г. Казанского университета работал там же в научно-исследовательском институте математики и механики, с 1970 г. на кафедре теоретической кибернетики.

Труды по дискретной математике и теории сложности.

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

Экспоненциальные нижние оценки сложности и пошагово моделирующие схемы // Кибернетика. 1987. № 4.

Нижние оценки сложности и сложность универсальных схем. Казань, 1990; Сложность булевых функций. Москва, 1991.

Models of lower-bounds proofs // Theoret. Comput. Sci. 1987. Volume 52.