Специальность ВАК:
01.01.09 (дискретная математика и математическая кибернетика)
Дата рождения:
14.04.1945
Сайт: https://www.math.spbu.ru/user/kos/kos/html Ключевые слова: вычислительная сложность,
нижние оценки сложности,
логика программ,
дискретная математика,
эвристики в решении задач,
неклассическая логика.
Основные темы научной работы:
Было получено простое диофантово представление последовательности решений уравнения Пелля (позже похожее представление было получено М. Дэвисом). Разработан вариант основания конструктивной теории вероятностей (как основа кандидатской диссертации). Для каждого натурального k приведен пример NP-полной задачи, для которой невозможен алгоритм ее решения с верхней оценкой времени его работы, являющейся полиномом степени 2k+1, на недетерминированной машине Тьюринга. Пример заключается в установлении существования коротких (длины, не превосходящей полинома степени k) решений у уравнений в битовых строках. Доказана невозможность полиномиального алгоритма для установления выполнимости булевых функциональных уравнений. Предложен полиномиальный по времени работы алгоритм решения систем строгих и нестрогих линейных неравенств с целыми коэффициентами. Ряд статей (совместно с А. В. Тишковым) были посвящены секвенциальному исчислению для смешанных многозначных логик Поста и логик Лукасевича. Было доказано, что задача разрешимости пропозиционального фрагмента этого исчисления принадлежит классу EXP-LIN-TIME (как собственному подклассу класса EXP-TIME). Задача выполнимости пропозициональных формул этого исчисления является NP-полной. Доказаны алгоритмическая неразрешимость универсальной теории кольца бинарно-рациональных чисел и разрешимость универсальной позитивной теории нестрогих неравенств как кольца рациональных чисел, так и кольца бинарно-рациональных чисел. Доказано, что задача разрешимости в вещественных числах строгих полиномиальных неравенств с целыми коэффициентами принадлежит классу NP. Для каждого постоянного модуля доказана PSPACE-полнота задачи разрешимости элементарной теории сравнений по этому модулю в кольце целых чисел.
Основные публикации:
Kossovski N. Sequentcalculus for generalization of Getmanova's logic to the predicates. // The Bulletin of Symbolic Logic. V. 1, no. 2, June 1995. P. 245.
Косовский Н. К., Тишков А. В. Логики конечнозначных предикатов на основе неравенств. Изд-во С. -Петербургского университета, 2000. 268 с.
Beauquier D., Kossovski N., Smirnova E. An algorithm for solvsbility testing of elementary linear inequalities systems // Abstracts of the 6th IMACS International IMACS Conference on Applications of Computer Algebra. St. Petersburg, 2000. P. 59–61.
Косовский Н. К. Сложность разрешимости некоторых дискретно нечетких систем // Математические вопросы кибернетики, вып. 9, 2000. С. 37–42.
Kossovski N. The consistency checking of strict polynomial inequalities // Proc. Intern. Workshop on Logic and Complexity in Computer Science, University Paris 12, Creteil, France, 2001, p. 149–152.
