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