Список нерешенных проблем информатики

Список нерешенных вычислительных задач

Эта статья представляет собой список заметных нерешенных проблем в области информатики . Проблема в информатике считается нерешенной, если решение не известно или когда эксперты в этой области расходятся во мнениях относительно предлагаемых решений.

Вычислительная сложность

• Проблема P и NP
• Какая связь между BQP и NP ?
• NC = P проблема
• NP = проблема со-NP
• P = проблема БПП
• P = проблема PSPACE
• L = проблема NL
• PH = проблема с PSPACE
• L = P проблема
• L = проблема RL
• Гипотеза об уникальных играх
• Верна ли гипотеза экспоненциального времени ?
  • Верна ли гипотеза сильной экспоненциальной зависимости времени (SETH)?
• Существуют ли односторонние функции ?
  • Возможна ли криптография с открытым ключом ?
• Гипотеза о логранге

Полиномиальное и недетерминированно-полиномиальное время для конкретных алгоритмических задач

• Можно ли выполнить факторизацию целых чисел за полиномиальное время на классическом (неквантовом) компьютере?
• Можно ли вычислить дискретный логарифм за полиномиальное время на классическом (неквантовом) компьютере?
• Можно ли вычислить кратчайший вектор решетки за полиномиальное время на классическом или квантовом компьютере?
• Можно ли решить проблему изоморфизма графов за полиномиальное время?
• Могут ли степени листа и степени k -листа быть распознаны за полиномиальное время?
• Можно ли решить игры на четность за полиномиальное время?
• Можно ли вычислить расстояние вращения между двумя двоичными деревьями за полиномиальное время?
• Можно ли распознать графы ограниченной кликовой ширины за полиномиальное время? ^[1]
• Можно ли найти простую замкнутую квазигеодезическую на выпуклом многограннике за полиномиальное время? ^[2]
• Можно ли найти одновременное вложение с фиксированными ребрами для двух заданных графов за полиномиальное время? ^[3]
• Можно ли решить задачу о сумме квадратного корня за полиномиальное время в модели машины Тьюринга?

Другие алгоритмические проблемы

• Гипотеза динамической оптимальности : имеют ли деревья расширения ограниченный коэффициент конкуренции?
• Можно ли построить дерево поиска в глубину в NC ?
• Можно ли вычислить быстрое преобразование Фурье за ​​время o ( n log n ) ?
• Какой самый быстрый алгоритм умножения двух n -значных чисел?
• Какова наименьшая возможная временная сложность сортировки Шелла в среднем случае с детерминированной последовательностью с фиксированным пропуском?
• Можно ли решить задачу 3SUM за строго субквадратичное время, то есть за время O ( n ^2−ϵ ) для некоторого ϵ>0 ?
• Можно ли вычислить расстояние редактирования между двумя строками длины n за строго субквадратичное время? (Это возможно только в том случае, если гипотеза сильной экспоненциальной зависимости времени неверна.)
• Можно ли выполнить сортировку X + Y за время o ( n ² log n ) ?
• Какой алгоритм умножения матриц самый быстрый ?
• Можно ли вычислить кратчайшие пути для всех пар за строго субкубическое время, то есть за время O ( V ^3−ϵ ) для некоторого ϵ>0 ?
• Можно ли дерандомизировать лемму Шварца - Циппеля для проверки полиномиальной идентичности ?
• Допускает ли линейное программирование строго полиномиальный алгоритм? (Это задача №9 в списке задач Смейла .)
• Сколько запросов необходимо, чтобы разрезать торт без зависти ?
• Какова алгоритмическая сложность задачи о минимальном остовном дереве ? Аналогично, какова сложность дерева решений проблемы MST? Оптимальный алгоритм вычисления MST известен , но он основан на деревьях решений, поэтому его сложность неизвестна.
• Гипотеза Гилберта – Поллака о соотношении Штейнера евклидовой плоскости.

Теория языка программирования

• POPLмарка
• Гипотеза Барендрегта–Геверса–Клопа

Другие проблемы

• Гипотеза Андераа – Карпа – Розенберга
• Гипотеза Черного
• Обобщенная проблема высоты звезды
• Проблема с разделением слов

Рекомендации

1. Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Зейдер, Стефан (2009), «Ширина клики NP-полна» (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi : 10.1137/070687256, MR  2519936, S2CID  18055798, заархивировано из оригинал (PDF) от 27 февраля 2019 г..
2. Демейн, Эрик Д .; О'Рурк, Джозеф (2007), «24 геодезические: Люстерник – Шнирельман», Алгоритмы геометрического складывания: связи, оригами, многогранники , Кембридж: Cambridge University Press, стр. 372–375, doi : 10.1017/CBO9780511735172, ISBN 978-0-521-71522-5, МР  2354878.
3. Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (2006), «Одновременные вложения графов с фиксированными краями» (PDF) , Теоретико-графовые концепции в информатике: 32-й международный семинар, WG 2006, Берген, Норвегия, 22–24 июня 2006 г., Пересмотренные статьи (PDF) , Конспекты лекций по информатике, вып. 4271, Берлин: Springer, стр. 325–335, номер документа : 10.1007/11917496_29, ISBN. 978-3-540-48381-6, МР  2290741.

Внешние ссылки

• Открытые проблемы, связанные с точными алгоритмами , Герхард Дж. Вегингер , Discrete Applied Mathematics 156 (2008) 397–405.
• Список открытых проблем RTA — открытые проблемы в рерайтинге .
• Список открытых задач TLCA — открытые проблемы в области лямбда-исчисления с типизированной областью .