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

Существуют ли проблемы в CS, где эффективные алгоритмы не известны, несмотря на теоремы существования, доказывающие, что такие эффективные алгоритмы должны существовать?

Как называются эти проблемы? Где я могу узнать больше?

В качестве примера Шелби Киммел использует метод противника в этой статье, чтобы показать, что должен существовать алгоритм запроса $O(1)$ для определенной задачи, для которой мы не знаем постоянного решения запроса. Она делает это особенно хитроумным способом, находя сложность запроса для задачи, составленной сам по себе $d$ раз, а затем находя сложность запроса $Q$ для составной функции, и отмечая, что сложность запроса исходной функции имеет порядок $Q^\frac{1}{d}$ .

Конечно, есть много примеров, по крайней мере, в духе вашего вопроса.

Часто такой результат получается из вероятностного метода . Например, одна статья, которая мне нравится, сталкивается с проблемой - реконструкция графов в аддитивной модели . Здесь авторы показывают, что существует набор запросов, которые (оптимально) изучат целевой граф. Учитывая этот набор, алгоритм эффективен. Тем не менее, они используют вероятностный метод, чтобы показать существование этого небольшого набора (для каждого размера задачи), который будет работать на всех входных данных, но явно не конструировать его. Поэтому лучшее, что они могут сделать, - это просто перебор по экспоненциальному семейству запросов, потому что они не имеют явной конструкции.$O(dn)$

Нет, вы всегда можете использовать самый быстрый и самый короткий алгоритм для всех четко определенных задач . ;)

Изменить: Ответ ниже касается существования решения данной вычислительной задачи, а не о существовании алгоритмов. Первоначально я неправильно истолковал вопрос.

Ответ

Существует класс сложности, который охватывает такие вычислительные проблемы. Это известно как TFNP . Это было определено в этой статье:

Нимрод Мегиддо и Христос Пападимитриу. Об общих функциях, теоремах существования и вычислительной сложности . Теоретическая информатика 81 (2): 317-324.

Здесь вы найдете такие проблемы, как Трихроматический треугольник, для которого существование решения гарантировано леммой Спернера (определение этой проблемы см. В статье).

У вас также есть следующий документ:

Христос Пападимитриу. О сложности аргумента о четности и других неэффективных доказательствах существования . Журнал компьютерных и системных наук 48 (3), 1990.

В этой статье вы найдете:

• В лемма -размерного Шпернера, которая является обобщением Trichromatic треугольника.$n$
• Равновесие 2-х игроков.
• Найти второй гамильтонов путь на графе.

В статье есть много примеров проблем такого типа. Поэтому я рекомендую взглянуть на это.