RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ЛОМИ, 1984, том 137, страницы 124–188 (Mi znsl4791)  

Эта публикация цитируется в 20 научных статьях (всего в 20 статьях)

Алгоритм полиномиальной сложности для разложения многочленов и нахождение компонент многообразия в субэкспоненциальное время

А. Л. Чистов


Аннотация: Описан алгоритм полиномиальной сложности для разложения многочленов от многих переменных на неприводимые множители над полем $P$ конечнопорожденным над простым подполем $H$. Построен также алгоритм для нахождения компонент проективного многообразия общих корней однородных многочленов $f_0,…,f_k\in F[X_0,…,X_n]$ (пусть $c-1$ обозначает его размерность) со временем работы полиномиальным от $(Ld^n)^{c+l}(q+1)$, где $\operatorname{deg}_{X_0,…,X_n}(f_i)<d$, число $L$ – размер представления многочленов $f_0,…,f_k$ и $l=\operatorname{deg}\operatorname{tr}_H(F)$, $q=\operatorname{char}(F)$.

Полный текст: PDF файл (4209 kB)

Реферативные базы данных:
Тип публикации: Статья
УДК: 518.5+512.46

Образец цитирования: А. Л. Чистов, “Алгоритм полиномиальной сложности для разложения многочленов и нахождение компонент многообразия в субэкспоненциальное время”, Теория сложности вычислений. II, Зап. научн. сем. ЛОМИ, 137, Изд-во «Наука», Ленинград. отд., Л., 1984, 124–188

Цитирование в формате AMSBIB
\RBibitem{Chi84}
\by А.~Л.~Чистов
\paper Алгоритм полиномиальной сложности для разложения многочленов и~нахождение компонент многообразия в~субэкспоненциальное время
\inbook Теория сложности вычислений.~II
\serial Зап. научн. сем. ЛОМИ
\yr 1984
\vol 137
\pages 124--188
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl4791}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=762101}
\zmath{https://zbmath.org/?q=an:0561.12010}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl4791
  • http://mi.mathnet.ru/rus/znsl/v137/p124

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Д. Ю. Григорьев, “Сложность разрешения теории первого порядка алгебраически замкнутых полей”, Изв. АН СССР. Сер. матем., 50:5 (1986), 1106–1120  mathnet  mathscinet  zmath; D. Yu. Grigor'ev, “The complexity of the decision problem for the first order theory of algebraically closed fields”, Math. USSR-Izv., 29:2 (1987), 459–475  crossref
    2. И. Е. Шпарлинский, “О некоторых вопросах теории конечных полей”, УМН, 46:1(277) (1991), 165–200  mathnet  mathscinet  zmath  adsnasa; I. E. Shparlinski, “On some problems in the theory of finite fields”, Russian Math. Surveys, 46:1 (1991), 199–240  crossref
    3. А. Л. Чистов, “Вычисление степени доминантного морфизма в нулевой характеристике за полиномиальное время. I”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. X, Зап. научн. сем. ПОМИ, 307, ПОМИ, СПб., 2004, 189–235  mathnet  mathscinet  zmath; A. L. Chistov, “Polynomial-time computation of the degree of a dominant morphism in characteristic zero. I”, J. Math. Sci. (N. Y.), 131:2 (2005), 5547–5568  crossref
    4. А. Л. Чистов, “Эффективная конструкция локальных параметров неприводимых компонент алгебраического многообразия в ненулевой характеристике”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. XIII, Зап. научн. сем. ПОМИ, 326, ПОМИ, СПб., 2005, 248–278  mathnet  mathscinet  zmath; A. L. Chistov, “Efficient construction of local parameters of irreducible components of an algebraic variety in nonzero characteristic”, J. Math. Sci. (N. Y.), 140:3 (2007), 480–496  crossref
    5. А. Л. Чистов, “Вычисление степени доминантного морфизма в нулевой характеристике за полиномиальное время. II”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. XII, Зап. научн. сем. ПОМИ, 325, ПОМИ, СПб., 2005, 181–224  mathnet  mathscinet  zmath; A. L. Chistov, “Polynomial-time computation of the degree of a dominant morphism in zero characteristic. II”, J. Math. Sci. (N. Y.), 138:3 (2006), 5733–5752  crossref
    6. А. Л. Чистов, “Вычисление степени доминантного морфизма в нулевой характеристике за полиномиальное время. III”, Теория представлений, динамические системы, комбинаторные методы. XV, Зап. научн. сем. ПОМИ, 344, ПОМИ, СПб., 2007, 203–239  mathnet  mathscinet; A. L. Chistov, “Polynomial-time computation of the degree of a dominant morphism in zero characteristic. III”, J. Math. Sci. (N. Y.), 147:6 (2007), 7234–7250  crossref
    7. А. Л. Чистов, “Дважды экспоненциальная нижняя оценка на степень системы образующих полиномиального простого идеала”, Алгебра и анализ, 20:6 (2008), 186–213  mathnet  mathscinet  zmath; A. L. Chistov, “Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal”, St. Petersburg Math. J., 20:6 (2009), 983–1001  crossref  isi
    8. А. Л. Чистов, “Вычисление степени доминантного морфизма в нулевой характеристике за полиномиальное время. IV”, Теория представлений, динамические системы, комбинаторные методы. XVI, Зап. научн. сем. ПОМИ, 360, ПОМИ, СПб., 2008, 260–294  mathnet  zmath; A. L. Chistov, “Polynomial-time computation of the degree of a dominant morphism in zero characteristic. IV”, J. Math. Sci. (N. Y.), 158:6 (2009), 912–927  crossref
    9. A. L. Chistov, “An overview of effective normalization of a nonsingular in codimension one projective algebraic variety”, Теория представлений, динамические системы, комбинаторные методы. XVII, Зап. научн. сем. ПОМИ, 373, ПОМИ, СПб., 2009, 295–317  mathnet; J. Math. Sci. (N. Y.), 168:3 (2010), 478–490  crossref
    10. А. Л. Чистов, “Алгоритмы полиномиальной сложности для новой модели представления алгебраических многообразий (в нулевой характеристике)”, Теория представлений, динамические системы, комбинаторные методы. XVIII, Зап. научн. сем. ПОМИ, 378, ПОМИ, СПб., 2010, 133–170  mathnet; A. L. Chistov, “Polynomial-time algorithms for a new model of representation of algebraic varieties (in characteristic zero)”, J. Math. Sci. (N. Y.), 174:1 (2011), 71–89  crossref
    11. A. L. Chistov, “Effective construction of a nonsingular in codimension one algebraic variety over a zero-characteristic ground field”, Теория представлений, динамические системы, комбинаторные методы. XIX, Зап. научн. сем. ПОМИ, 387, ПОМИ, СПб., 2011, 167–188  mathnet; J. Math. Sci. (N. Y.), 179:6 (2011), 729–740  crossref
    12. A. L. Chistov, “An improvement of the complexity bound for solving systems of polynomial equations”, Теория представлений, динамические системы, комбинаторные методы. XX, Зап. научн. сем. ПОМИ, 390, ПОМИ, СПб., 2011, 299–306  mathnet; J. Math. Sci. (N. Y.), 181:6 (2012), 921–924  crossref
    13. А. Л. Чистов, “Оценка степени системы уравнений, задающей многообразие приводимых многочленов”, Алгебра и анализ, 24:3 (2012), 199–222  mathnet  mathscinet  zmath  elib; A. L. Chistov, “Estimating the power of a system of equations that determines a variety of reducible polynomials”, St. Petersburg Math. J., 24:3 (2013), 513–528  crossref  isi  elib
    14. А. Л. Чистов, “Эффективная версия первой теоремы Бертини в ненулевой характеристике и еë приложения”, Теория представлений, динамические системы, комбинаторные методы. XXI, Зап. научн. сем. ПОМИ, 403, ПОМИ, СПб., 2012, 172–196  mathnet  mathscinet; A. L. Chistov, “An effective version of the first Bertini theorem in nonzero characteristic and its applications”, J. Math. Sci. (N. Y.), 190:3 (2013), 503–514  crossref
    15. А. Л. Чистов, “Детерминированный алгоритм полиномиальной сложности для первой теоремы Бертини. I”, Теория представлений, динамические системы, комбинаторные методы. XXII, Зап. научн. сем. ПОМИ, 411, ПОМИ, СПб., 2013, 191–239  mathnet  mathscinet; A. L. Chistov, “A deterministic polynomial-time algorithm for the first Bertini theorem. I”, J. Math. Sci. (N. Y.), 196:2 (2014), 223–243  crossref
    16. А. Л. Чистов, “Детерминированный алгоритм полиномиальный сложности для первой теоремы Бертини. II”, Теория представлений, динамические системы, комбинаторные методы. XXIII, Зап. научн. сем. ПОМИ, 421, ПОМИ, СПб., 2014, 214–249  mathnet; A. L. Chistov, “A deterministic polynomial-time algorithm for the first Bertini theorem. II”, J. Math. Sci. (N. Y.), 200:6 (2014), 769–784  crossref
    17. А. Л. Чистов, “Детерминированный алгоритм полиномиальной сложности для первой теоремы Бертини. III”, Теория представлений, динамические системы, комбинаторные методы. XXIV, Зап. научн. сем. ПОМИ, 432, ПОМИ, СПб., 2015, 297–323  mathnet; A. L. Chistov, “A deterministic polynomial-time algorithm for the first Bertini theorem. III”, J. Math. Sci. (N. Y.), 209:6 (2015), 1005–1019  crossref
    18. А. Л. Чистов, “Расширение алгоритма Ньютона–Пюизе на случай ненулевой характеристики основного поля. I”, Алгебра и анализ, 28:6 (2016), 147–188  mathnet; A. L. Chistov, “Extension of the Newton–Puiseux algorithm to the case of a nonzero characteristic ground field. I”, St. Petersburg Math. J., 28:6 (2017), 825–853  crossref  isi  elib
    19. А. Л. Чистов, “Системы с параметрами, или эффективное решение систем полиномиальных уравнений 33 года спустя. I”, Теория представлений, динамические системы, комбинаторные методы. XXVIII, Зап. научн. сем. ПОМИ, 462, ПОМИ, СПб., 2017, 122–166  mathnet; A. L. Chistov, “Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. I”, J. Math. Sci. (N. Y.), 232:2 (2018), 177–203  crossref
    20. А. Л. Чистов, “Системы с параметрами, или эффективное решение систем полиномиальных уравнений 33 года спустя. II”, Теория представлений, динамические системы, комбинаторные методы. XXIX, Зап. научн. сем. ПОМИ, 468, ПОМИ, СПб., 2018, 138–176  mathnet; A. L. Chistov, “Systems with parameters, or efficiently solving systems of polynomial equations: 33 years later. II”, J. Math. Sci. (N. Y.), 240:5 (2019), 594–616  crossref
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:274
    Полный текст:61
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020