Вычислительная сложность фрагментов теории поля комплексных чисел
В статье обсуждена вычислительная сложность формул в предварённой форме с ограничением на число перемен кванторов. В частности, говорится о теории алгебраически замкнутых полей. Доказано, что распознавание вершин многомерного куба на гиперплоскости сводится к распознаванию особых точек на гиперпове...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Academician Ye.A. Buketov Karaganda University
2015-03-01
|
| Series: | Қарағанды университетінің хабаршысы. Математика сериясы |
| Subjects: | |
| Online Access: | http://mathematics-vestnik.ksu.kz/index.php/mathematics-vestnik/article/view/10 |
| Summary: | В статье обсуждена вычислительная сложность формул в предварённой форме с ограничением на число перемен кванторов. В частности, говорится о теории алгебраически замкнутых полей. Доказано, что распознавание вершин многомерного куба на гиперплоскости сводится к распознаванию особых точек на гиперповерхности, построенной за полиномиальное время. Более того, доказаны некоторые соотношения между классами сложности. Даны рекомендации по улучшению концепции сложности, а также связи с теорией моделей.
|
|---|---|
| ISSN: | 2518-7929 2663-5011 |