Эта статья представляет собой список заметных нерешенных проблем в области информатики . Проблема в информатике считается нерешенной, если решение не известно или когда эксперты в данной области не согласны с предлагаемыми решениями.
Вычислительная сложность
- Проблема P против NP
- Какая связь между BQP и NP ?
- NC = P проблема
- NP = проблема совместного NP
- P = проблема BPP
- P = проблема PSPACE
- L = проблема NL
- PH = проблема PSPACE
- L = P проблема
- L = проблема RL
- Гипотеза уникальных игр
- Верна ли гипотеза экспоненциального времени ?
- Верна ли сильная гипотеза экспоненциального времени (SETH)?
- Есть ли односторонние функции существуют?
- Возможна ли криптография с открытым ключом ?
- Гипотеза лог-ранга
Сравнение полиномиального и неполиномиального времени для конкретных алгоритмических задач
- Может ли целочисленная факторизация быть произведена за полиномиальное время на классическом (не квантовом) компьютере?
- Можно ли вычислить дискретный логарифм за полиномиальное время?
- Можно ли вычислить кратчайший вектор решетки за полиномиальное время на классическом или квантовом компьютере?
- Можно ли найти сгруппированные плоские чертежи за полиномиальное время?
- Можно ли решить проблему изоморфизма графов за полиномиальное время?
- Можно ли распознать степени и k -листные степени за полиномиальное время?
- Можно ли решить игры на четность за полиномиальное время?
- Можно ли вычислить расстояние вращения между двумя двоичными деревьями за полиномиальное время?
- Можно ли распознать графы ограниченной ширины клики за полиномиальное время? [1]
- Можно ли найти простую замкнутую квазигеодезическую на выпуклом многограннике за полиномиальное время? [2]
- Можно ли за полиномиальное время найти одновременное вложение с фиксированными ребрами для двух данных графов? [3]
Другие алгоритмические проблемы
- Гипотеза динамической оптимальности : имеют ли растянутые деревья ограниченное конкурентное отношение?
- Есть ли k -конкурентный онлайн-алгоритм для задачи k- сервера ?
- Можно ли построить дерево поиска в глубину в NC ?
- Можно ли вычислить быстрое преобразование Фурье за время o ( n log n ) ?
- Какой самый быстрый алгоритм умножения двух n- значных чисел?
- Какова минимально возможная средняя временная сложность Shellsort с детерминированной последовательностью с фиксированными промежутками?
- Можно ли решить 3SUM за строго субквадратичное время, то есть за время O ( n 2 − ϵ ) для некоторого ϵ> 0 ?
- Можно ли вычислить расстояние редактирования между двумя строками длины n за строго субквадратичное время? (Это возможно только в том случае, если сильная гипотеза экспоненциального времени неверна.)
- Может X + Y сортировка быть сделаны в O ( п 2 журнала п ) время?
- Какой алгоритм умножения матриц самый быстрый ?
- Можно ли вычислить кратчайшие пути для всех пар за строго субкубическое время, то есть за время O ( V 3 − ϵ ) для некоторого ϵ> 0 ?
- Может ли лемма Шварца-Zippel для полиномиальной проверки идентичности быть derandomized ?
- Допускает ли линейное программирование алгоритм с сильно полиномиальным временем? (Это проблема № 9 в списке проблем Смейла .)
- Сколько запросов требуется, чтобы разрезать торт без зависти ?
- Каков алгоритм поисковой таблицы, которая последовательно генерирует игровые лабиринты в игре Entombed для Atari 2600 1982 года, просто исходя из значений пяти пикселей, соседних с последующими, которые должны быть сгенерированы?
- Какова алгоритмическая сложность задачи о минимальном остовном дереве ? Какова же сложность дерева решений проблемы MST? Оптимальный алгоритм для вычисления MST известен , но он основан на деревьях решений, поэтому его сложность неизвестна.
Алгоритмы обработки естественного языка
- Есть ли в английском языке идеальный алгоритм слогового написания ?
- Есть ли в английском языке идеальный алгоритм стемминга ?
- Есть ли какой-нибудь идеальный алгоритм разделения фраз на английском языке?
- Как компьютеры могут распознать двусмысленность местоимений в английском языке? (Также известный как Winograd Schema Challenge ).
Теория языка программирования
- POPLmark
- Гипотеза Барендрегта – Геверса – Клопа
Другие проблемы
- Гипотеза Андераа – Карпа – Розенберга
- Обобщенная проблема высоты звезды
- Проблема разделения слов
Рекомендации
- ^ Товарищи, Майкл Р .; Розамонд, Фрэнсис А .; Ротикс, Уди; Шейдер, Стефан (2009), «Ширина клики является NP-полной» (PDF) , SIAM Journal on Discrete Mathematics , 23 (2): 909–939, doi : 10.1137 / 070687256 , MR 2519936 , заархивировано из оригинала (PDF ) на 2019-02-27.
- ^ Демейн, Эрик Д .; О'Рурк, Джозеф (2007), «24 геодезических: Люстерник – Шнирельман», геометрические алгоритмы складывания: связи, оригами, многогранники , Кембридж: Cambridge University Press, стр. 372–375, DOI : 10.1017 / CBO9780511735172 , ISBN 978-0-521-71522-5, MR 2354878.
- ^ Гасснер, Элизабет; Юнгер, Михаэль; Percan, Merijam; Шефер, Маркус; Шульц, Майкл (2006), «Одновременные вложения графов с фиксированными ребрами» (PDF) , Теоретико- графические концепции в компьютерных науках: 32-й международный семинар, WG 2006, Берген, Норвегия, 22-24 июня 2006 г., Revised Papers (PDF) , Лекции по информатике, 4271 , Берлин: Springer., С. 325-335, DOI : 10.1007 / 11917496_29 , MR 2290741.
Внешние ссылки
- Открытые проблемы вокруг точных алгоритмов по Gerhard J. Woeginger , дискретная прикладной математики 156 (2008) 397-405.
- Список открытых проблем RTA - открытые проблемы в переписывании .
- Список открытых проблем TLCA - открытые проблемы в области лямбда-исчисления с типизированной областью .