Список нерешенных проблем информатики - List of unsolved problems in computer science

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

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

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

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

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

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

В гипотеза динамической оптимальности: есть ли у растянутых деревьев ограниченное конкурентное отношение?
Есть ли $k$ -конкурентный онлайн-алгоритм для $k$ -сервер проблема ?
Может ли дерево поиска в глубину быть построенным в NC ?
Может ли быстрое преобразование Фурье быть вычисленным в $о (п бревно п)$ время?
Какой самый быстрый алгоритм умножения из двух п-цифровые числа?
Какова наименьшая возможная средняя временная сложность Shellsort с детерминированной последовательностью с фиксированным разрывом?
Может 3SUM решаться за строго субквадратичное время, то есть за время $О (п 2 - ϵ)$ для некоторых $ϵ> 0$ ?
Может ли редактировать расстояние между двумя строками длины $п$ вычисляться за строго субквадратичное время? (Это возможно только при сильном гипотеза экспоненциального времени ложно.)
Может X + Y сортировка быть сделано в $о (п 2)$ время?
Какой самый быстрый алгоритм умножения матриц ?
Может кратчайшие пути для всех пар вычисляться за строго субкубическое время, то есть за время $О (V 3 - ϵ)$ для некоторых $ϵ> 0$ ?
Может ли Лемма Шварца – Циппеля. за проверка полиномиальной идентичности быть дерандомизированный ?
Делает линейное программирование признать сильно полиномиальный -временной алгоритм? (Это проблема №9 в Список Смейла проблем.)
Сколько запросов требуется для резка торта без зависти ?
Каков алгоритм Справочная таблица который постоянно генерирует игровые лабиринты в 1982 году. Atari 2600 игра Погребенный просто из значений пяти пикселей, соседних с последующими, которые должны быть сгенерированы?

Алгоритмы обработки естественного языка

Есть ли идеальный слоговая форма алгоритм на английском языке?
Есть ли идеальный остановка алгоритм на английском языке?
Есть ли идеальный POS-теги алгоритм на английском языке?
Как компьютеры распознают двусмысленность местоимения на английском языке? (Также известен как Вызов схемы Винограда ).

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

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

внешняя ссылка

Открытые проблемы вокруг точных алгоритмов к Герхард Й. Вёгингер, Дискретная прикладная математика 156 (2008) 397–405.
Список открытых проблем RTA - открытые проблемы в переписывание.
Список открытых проблем TLCA - открытые проблемы в области типизированное лямбда-исчисление.

[1] Товарищи, Майкл Р.; Розамонд, Фрэнсис А.; Ротикс, Уди; Зейдер, Стефан (2009), «Ширина клики NP-полная» (PDF), Журнал SIAM по дискретной математике, 23 (2): 909–939, Дои:10.1137/070687256, МИСТЕР 2519936.

[2] Демейн, Эрик Д.; О'Рурк, Джозеф (2007), «24 геодезических: Люстерник – Шнирельманн», Алгоритмы геометрического складывания: Связи, оригами, многогранники, Кембридж: Издательство Кембриджского университета, стр. 372–375, Дои:10.1017 / CBO9780511735172, ISBN 978-0-521-71522-5, МИСТЕР 2354878.

[3] Гасснер, Элизабет; Юнгер, Михаэль; Percan, Merijam; Шефер, Маркус; Шульц, Майкл (2006), «Одновременные вложения графов с фиксированными ребрами» (PDF), Теоретико-графические концепции в компьютерных науках: 32-й международный семинар, WG 2006, Берген, Норвегия, 22-24 июня 2006 г., исправленные статьи (PDF), Конспект лекций по информатике, 4271, Берлин: Springer, стр. 325–335, Дои:10.1007/11917496_29, МИСТЕР 2290741.

[1]

[2]

[3]