Я ищу список об известной или неизвестной сложности различных теоретико-алгебраических задач. Например,
- GCD в открыт,
- факторинг в открыт,
- вычисление когомологий пучка -hard ,
- Арора и Барак утверждают, что вариант факторинга является -полным (хотя это не ясно из обсуждения в NP-полной версии факторинга. ),
- Революционная работа Барбулеску и др. Над дискретными логарифмами .
Адлеман однажды опубликовал список, сосредоточенный на и N P, но он кажется устаревшим. У Мамфорда есть статья о том, что вычислимо в алгебраической геометрии без учета сложности.
Кто-нибудь знает список (основных) открытий, так как эти списки были опубликованы?
Каковы некоторые проблемы теоретико-алгебраической теории чисел, классы сложности которых, возможно, уже известны (поскольку вышеприведенные списки были опубликованы), неизвестны, но предположительны, или неизвестны и не предположены?
Некоторыми путями проблем могут быть задачи интерполяции (одномерные или многомерные по различным полям), теорема об остатках в Китае, сложность подсчета точек по кривым и т. Д.
Ответы:
Алгебраическая геометрия
Существует несколько ( arXiv ) новых алгоритмов для вычисления топологических инвариантов сложных многообразий (с различными ограничениями, такими как гладкость и т. Д.). Я считаю, что для большинства из них оптимальная верхняя граница все еще открыта.
Проблемы изоморфизма
Другой
источник
Добавим еще несколько с акцентом на теорию Галуа и вычислительную теорию Галуа (см. Связанный вопрос на cs.SE ):
воспроизведено из связанного вопроса по МО
источник