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

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

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

Проблема 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 2 войти) время$ ?
Какой самый быстрый алгоритм умножения матриц ?
Можно ли вычислить кратчайшие пути для всех пар за строго субкубическое время, то есть за время $O (V 3-ϵ)$ для некоторого $ϵ>0$ ?
Можно ли Шварца-Циппеля для проверки полиномиальной идентичности лемму дерандомизировать ?
ли линейное программирование Допускает строго полиномиальный алгоритм? (Это задача №9 в Смейла .) списке задач
Сколько запросов необходимо, чтобы разрезать торт без зависти ?
Какова алгоритмическая сложность задачи о минимальном остовном дереве ? Аналогично, какова сложность дерева решений проблемы MST? Оптимальный алгоритм вычисления MST известен , но он основан на деревьях решений, поэтому его сложность неизвестна.
Гипотеза Гилберта – Поллака : ли отношение Штейнера евклидовой плоскости равно $2/{\sqrt {3}}$ ?

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

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

Верна ли гипотеза Андераа–Карпа–Розенберга ?
Гипотеза Черного : если детерминированный конечный автомат с $n$ у состояний есть синхронизирующее слово , должно ли оно иметь длину не более $(n-1)^{2}$ ?
Обобщенная проблема высоты звезды : могут ли все регулярные языки быть выражены с использованием обобщенных регулярных выражений с ограниченной глубиной вложенности звезд Клини ?
Проблема разделения слов : сколько состояний необходимо детерминированному конечному автомату , который ведет себя по-разному на двух заданных строках длины $n$ ?
Каков статус полноты по Тьюрингу всех уникальных элементарных клеточных автоматов ?

Ссылки

^ Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Зейдер, Стефан (2009), «Ширина клики NP-полна» (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi : 10.1137/070687256 , MR 2519936 , S2CID 18055798 , заархивировано из оригинал (PDF) от 27 февраля 2019 г.
^ Демейн, Эрик Д .; О'Рурк, Джозеф (2007), «24 геодезические: Люстерник – Шнирельман», Алгоритмы геометрического складывания: связи, оригами, многогранники , Кембридж: Cambridge University Press, стр. 372–375, doi : 10.1017/CBO9780511735172 , ISBN 978-0-521-71522-5 , МР 2354878 .
^ Гасснер, Элизабет; Юнгер, Майкл; Перкан, Мериям; Шефер, Маркус; Шульц, Майкл (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 — открытые задачи в области лямбда-исчисления с типизированной областью .

[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 .

[1]

[2]

[3]