Abstract: Рассматривается серия известных и естественных представлений для упорядоченного поля вещественных алгебраических чисел. Доказано, что все они полиномиально эквивалентны друг другу. Приводится общая теорема, объясняющая этот эффект. В ходе анализа этих представлений вводится понятие фактор-структуры. Показано, что вопрос о полиномиальной эквивалентности произвольной полиномиально вычислимой фактор-структуры и обычной структуры почти эквивалентен проблеме P=NP. Приводятся некоторые условия, при которых ответ положителен.

Cite: Алаев П.Е. , Селиванов В.Л.
Поля алгебраических чисел, вычислимые за полиномиальное время. II
Алгебра и логика. 2021. Т.60. №6. С.533-548. DOI: 10.33048/alglog.2021.60.601

Translated: Alaev P.E. , Selivanov V.L.
Fields of Algebraic Numbers Computable in Polynomial Time. II
Algebra and Logic. 2021. V.60. N6. P.349 - 359. DOI: 10.1007/s10469-022-09661-3 WOS Scopus OpenAlex

Identifiers: No identifiers

Citing: Пока нет цитирований

Altmetrics: