Abstract:
В статье обсуждена вычислительная сложность формул в предварённой форме с ограничением на
число перемен кванторов. В частности, говорится о теории алгебраически замкнутых полей. Доказано,
что распознавание вершин многомерного куба на гиперплоскости сводится к распознаванию особых
точек на гиперповерхности, построенной за полиномиальное время. Более того, доказаны некоторые
соотношения между классами сложности. Даны рекомендации по улучшению концепции сложности,
а также связи с теорией моделей.
