Список теоретико-числовых или алгебраических задач в различных классах сложности

12

Я ищу список об известной или неизвестной сложности различных теоретико-алгебраических задач. Например,

Адлеман однажды опубликовал список, сосредоточенный на и N P, но он кажется устаревшим. У Мамфорда есть статья о том, что вычислимо в алгебраической геометрии без учета сложности.PNP

Кто-нибудь знает список (основных) открытий, так как эти списки были опубликованы?

Каковы некоторые проблемы теоретико-алгебраической теории чисел, классы сложности которых, возможно, уже известны (поскольку вышеприведенные списки были опубликованы), неизвестны, но предположительны, или неизвестны и не предположены?

Некоторыми путями проблем могут быть задачи интерполяции (одномерные или многомерные по различным полям), теорема об остатках в Китае, сложность подсчета точек по кривым и т. Д.

Т ....
источник
Вы действительно хотите только проблемы, сложность которых не только не известна, но даже не предполагается, что они где-то есть? Это кажется довольно ограничительным, например, целочисленная факторизация не удовлетворила бы этот вопрос, поскольку предполагается, что он находится в промежуточном положении между P и ... Но я думаю (и надеюсь), что вы имеете в виду чуть более разрешающий вопрос. Было бы интересно увидеть такой список. UPcoUP
Джошуа Грохув
@ JoshuaGrochow расширился.
T ....
Известно ли, что GCD находится в пространстве журнала?
4
Нет, это открытая проблема, находится ли она где-нибудь в иерархии ЧПУ.
Эмиль Йержабек

Ответы:

18

Алгебраическая геометрия

  • EXPSPACEPPVP¯PSPACE

  • AMcoAMNP#P

  • Существует несколько ( arXiv ) новых алгоритмов для вычисления топологических инвариантов сложных многообразий (с различными ограничениями, такими как гладкость и т. Д.). Я считаю, что для большинства из них оптимальная верхняя граница все еще открыта.

  • AMNP

  • Ed+3dEnnEn+1такие генераторы. Таким образом, текущая верхняя граница разрешения особенностей может быть далека от истины, но мало что известно на самом деле.

Проблемы изоморфизма

  • NPcoAMNPcoNPP

  • 2O(n)|G|2O(n)

  • TIME(nO(logn))PP

Другой

  • FFQNPNPNP

  • QNPNP

PRIMESP

Джошуа Грохов
источник
Я удивлен, что HN в NP неизвестно. Все, что вам нужно сделать, это проверить решение для каждого полинома правильно?
T ....
Каков разрыв в разрешении особенностей?
T ....
4
@Turbo: Для HN полиномы являются целочисленными полиномами, но решения могут быть комплексными числами, которые даже не должны быть выражаемыми конечным числом битов, не говоря уже о полиномиальном количестве битов. Кроме того, даже чтобы получить AM, я думаю, что вам нужен GRH.
Джошуа Грохоу
2
(Сначала я подтверждаю, что доказательство того, что HN находится в AM, основано на GRH.) @Turbo: входные данные представляют собой набор целочисленных полиномов, определяемых конечным числом битов. Очевидным сертификатом для HN будет решение системы. Но Джошуа говорит, что описание такого решения не обязательно представимо с конечным числом битов. Таким образом, мы далеки от того, чтобы иметь сертификат полиномиального размера !
Бруно
3
@Nikhil: потому что PIT не дает верхней границы NNL. Наборы удара черного ящика - то, что дает предел. Проблема с перечислением всех возможных наборов попаданий для NNL (алгоритм PSPACE для PIT) заключается в том, что для каждого из них необходимо проверять определенное свойство, и эта проверка известна только в EXPSPACE. Если OTOH, вы можете напрямую создать гарантированный ударный набор, в основном вам не нужно проверять. Вы увидите, когда прочитаете газету.
Джошуа Грохов