Алгоритмические проблемы алгебраических систем и анализ сложности алгоритмов
Full Name of the work head: Темирбеков Н.М.
Исполнители проекта: Хисамиев Н.Г.*
: Восточно-Казахстанский государственный технический университет им. Д.Серикбаева
Inventory number: 0214РК00062
Registration number: 0113РК00887
Keywords: нильпотентные группы*вычислимость групп*распознавание булевых алгебр*алгебраические системы*
Получены необходимые и достаточные условия для вербальной и экзистенциальной замкнутости подгруппы свободной нильпотентной группы конечного ранга и вычислимости нильпотентных групп конечных размерностей и подгрупп группы унитреугольных матриц. Установлено существование главной вычислимой нумерации класса всех вычислимых нильпотентных групп конечных размерностей. Получены нижние оценки на временную сложность распознавания всей теории булевых алгебр, так и ее фрагмента. Изучены младшие классы полиномиально-ограниченной иерархии языков. Доказано, что число классов Р-иерархии языков конечно. Установлено совпадение классов языков, распознаваемых за экспоненциальное время, с классом языков, распознаваемых с полиномиальной памятью. Усовершенствован полиномиальный алгоритм Визинга-Назарца для классификации вершин простого связного графа, разбивающий множество его вершин на орбиты, при условии, что граф удовлетворяет определенным требованиям.*
