Вычислительная сложность фрагментов теории поля комплексных чисел
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Изд-во КарГУ
Abstract
В статье обсуждена вычислительная сложность формул в предварённой форме с ограничением на
число перемен кванторов. В частности, говорится о теории алгебраически замкнутых полей. Доказано,
что распознавание вершин многомерного куба на гиперплоскости сводится к распознаванию особых
точек на гиперповерхности, построенной за полиномиальное время. Более того, доказаны некоторые
соотношения между классами сложности. Даны рекомендации по улучшению концепции сложности,
а также связи с теорией моделей.
Description
Citation
Латкин И.В. Вычислительная сложность фрагментов теории поля комплексных чисел/ И.В.Латкин, А.В.Селиверстов// Қарағанды универисетінің хабаршысы. Математика Сериясы.=Вестник Карагандинского университета. Серия Математика.=Bulletin of the Karaganda University. Mathematics Series. - 2015. - №1. - С. 47-55.