|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Поля алгебраических чисел, вычислимые за полиномиальное время. II
П. Е. Алаевa, В. Л. Селивановba a Ин-т матем. им. С. Л. Соболева СО РАН, г. Новосибирск, РОССИЯ
b Ин-т сист. информ. им. А. П. Ершова СО РАН, г. Новосибирск, РОССИЯ
Аннотация:
Продолжается работа авторов [Алгебра и логика, 58, № 6 (2019), 673—705], в которой были построены представления поля комплексных алгебраических чисел и упорядоченного поля вещественных алгебраических чисел, вычислимые за полиномиальное время. Здесь рассматриваются другие известные и естественные представления для этих полей. Доказывается, что все они полиномиально эквивалентны друг другу. Приводится общая теорема, объясняющая этот эффект.
В ходе анализа этих представлений вводится понятие фактор-структуры. Показывается, что вопрос о полиномиальной эквивалентности произвольной полиномиально вычислимой фактор-структуры и обычной структуры почти эквивалентен проблеме ${\rm P=NP}$. Приводятся некоторые условия, при которых ответ положителен.
Ключевые слова:
поле алгебраических чисел, полиномиально вычислимая структуры, полиномиально эквивалентные структуры.
Поступило: 15.01.2021 Окончательный вариант: 08.04.2022
Образец цитирования:
П. Е. Алаев, В. Л. Селиванов, “Поля алгебраических чисел, вычислимые за полиномиальное время. II”, Алгебра и логика, 60:6 (2021), 533–548
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2684 https://www.mathnet.ru/rus/al/v60/i6/p533
|
Статистика просмотров: |
Страница аннотации: | 143 | PDF полного текста: | 31 | Список литературы: | 24 | Первая страница: | 6 |
|