Вычислительная сложность фрагментов теории поля комплексных чисел - Латкин, И.В.; Селиверстов, А.В. (Изд-во КарГУ, 2015)
В статье обсуждена вычислительная сложность формул в предварённой форме с ограничением на число перемен кванторов. В частности, говорится о теории алгебраически замкнутых полей. Доказано, что распознавание вершин многомерного куба на гиперплоскости сводится к распознаванию особых точек на гиперповерхности, построенной за полиномиальное время. Более того, доказаны некоторые соотношения между классами сложности. Даны рекомендации по улучшению концепции сложности, а также связи с теорией моделей.
Кешен сандар өрісі теориясының есептелімділік күрделілік тұстары
Computational complexity of fragments of the theory of complex numbers
Keywords: вычислительная сложность; теория первого порядка; комплексные числа; перемена кванторов; иерархия классов