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

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

Содержание

• 1 Вычислительная сложность
• 2 Полиномиальное и неполиномиальное время для конкретных алгоритмических проблем
• 3 Другие алгоритмические проблемы
• 4 Алгоритмы обработки естественного языка
• 5 Теория языка программирования
• 6 Другие проблемы
• 7 Ссылки
• 8 Внешние ссылки

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

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

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

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

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

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

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

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

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

• POPLmark
• гипотеза Барендрегта – Гёверса – Клопа

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

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

Ссылки

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

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