Проблемы предполагаются, но не оказываются легкими

У нас много проблем, таких как факторизация, которые сильно предположили, но не доказали, что они находятся вне P. Есть ли вопросы с противоположным свойством, а именно, что они сильно предположены, но не доказано, что они находятся внутри P?

Два десятилетия назад одним из правдоподобных ответов было бы тестирование простоты : существовали алгоритмы, которые выполнялись в рандомизированном полиномиальном времени, и алгоритмы, которые выполнялись в детерминистическом полиномиальном времени при вероятной гипотезе, основанной на теории чисел, но не было известных детерминированных алгоритмов полиномиального времени. В 2002 году Agrawal, Kayal и Saxena изменили результат, согласно которому тестирование на первичность выполняется в P. Итак, мы больше не можем использовать этот пример.

Я бы поставил тестирование полиномиальной идентичности в качестве примера проблемы, которая имеет хорошие шансы оказаться в P, но там, где никто не смог доказать это. Мы знаем о рандомизированных алгоритмах полиномиального времени для проверки полиномиальной идентичности, но нет детерминированных алгоритмов. Однако есть веские причины полагать, что рандомизированные алгоритмы могут быть дерандомизированы.

Например, в криптографии настоятельно полагают, что существуют высоконадежные псевдослучайные генераторы (например, AES-CTR является одним из разумных кандидатов). И если это правда, тогда проверка полиномиальной идентичности должна проводиться в P. (Например, используйте фиксированное начальное число, применяйте генератор псевдослучайных данных и используйте его выход вместо случайных битов; для этого не хватило бы огромного заговора. ) Это можно сделать формальным, используя модель случайного оракула; если у нас есть хеш-функции, которые могут быть соответствующим образом смоделированы моделью случайного оракула, то из этого следует, что существует детерминированный алгоритм за полиномиальное время для проверки полиномиальной идентичности.

Для более детальной проработки этого аргумента см. Также мой ответ по связанной теме и мои комментарии по смежному вопросу .

$P=NP$

$P$

Но, опять же, никто не знает.

$P$$P$$P$

$\sf NP\cap coNP$$e^{O(\sqrt{n})}$$n$$\sf P$