Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №9, Москва, 2000
Авторы: Косовский Н.К.
Сложность разрешимости некоторых дискретно нечётких систем
Аннотация:
Рассматриваются задачи разрешимости (и сложности разрешимости) теорий в некоторых сигнатурах при различных носителях. Доказана разрешимость алгоритмом из класса EXPTIME универсальной позитивной теории сигнатуры ⟨ ̅Q0;|PolQ0,max,min,≤ ⟩, в которой коэффициенты и степень полиномов записываются в двоичной системе счисления. Кроме этого, доказана разрешимость универсальной позитивной теории колец всех k-ично рациональных чисел, больших заданной константы, и всех k-ично рациональных чисел, не больших заданной константы. Доказана NP-трудность всех этих задач. Доказана также алгоритмическая неразрешимость универсальных теорий колец всех k-ично рациональных чисел при k ≥ 2. Последняя задача может рассматриваться как компьютерно ориентированная модификация проблемы разрешимости универсальной теории поля рациональных чисел.
Ключевые слова:
алгоритмическая разрешимость, вычислительная сложность, универсальные теории рациональных чисел
Язык публикации: русский, страниц: 6 (с. 37-42)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Косовский Николай Кириллович,  ,  Санкт-Петербургский государственный университет