Специальность ВАК:
01.01.06 (математическая логика, алгебра и теория чисел)
Дата рождения:
07.07.1950
E-mail: Ключевые слова: рекурсивно перечислимые множества; степени неразрешимости; сложность вычислимости.
Основные темы научной работы:
Доказано, что в каждой нерекурсивной рекурсивно перечислимой $T$-степени содержится бесконечное число попарно $Q$-несравнимиых неускоряемых множеств и в полной $T$-степени целиком содержится бесконечное число попарно $Q$-несравнимиых неускоряемых $Q$-степеней. Показано, что среди всех $m$-степеней, содержащихся в $Q$-степени максимального множества, есть наименьшая $m$-степень и $Q$-степень максимального множества не является точной верхней гранью ни для каких несравнимых $Q$-степеней. Доказано, что верхняя полурешетка рекурсивно перечислимых $sQ$-степеней упорядечно плотно и для каждой нерекурсивной рекурсивно перечислимой $sQ$-степени сушествует несравнмая с ней неускоремая $sQ$-степень. Показано, что понятия сильно эффективно ускореемого множества и рекурсивно перечислимого $sQ$-пелного множества эквивалентны.
Основные публикации:
Оманадзе Р. Ш. О верхней полурешетке рекурсивно перечислимых $Q$-степеней // Алгебра и логика, 1984, 23, 2, 175–184.
Оманадзе Р. Ш. Классы рекурсивно перечислимых множеств и $Q$-сводимость // Матем. заметки, 1989, 45, 2, 79–82.
Оманадзе Р. Ш. О верхней полурешетке рекурсивно перечислимых $sQ$-степеней // Алгебра и логика, 1991, 30, 4, 405–413.
Оманадзе Р. Ш. Соотношения между некоторыми сводимостями // Алгебра и логика, 1994, 33, 6, 681–688.
Оманадзе Р. Ш. Сложностные свойства рекурсивно перечислимых множеств и $sQ$-полнота // Матем. заметки, 1997, 62, 3, 425–429.
