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

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

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

• Проблема 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 ^{2 − ϵ} ) для некоторого ϵ> 0 ?
• Можно ли вычислить расстояние редактирования между двумя строками длины n за строго субквадратичное время? (Это возможно только в том случае, если сильная гипотеза экспоненциального времени неверна.)
• Может X + Y сортировка быть сделаны в O ( п ² журнала п ) время?
• Какой алгоритм умножения матриц самый быстрый ?
• Можно ли вычислить кратчайшие пути для всех пар за строго субкубическое время, то есть за время O ( V ^{3 − ϵ} ) для некоторого ϵ> 0 ?
• Может ли лемма Шварца-Zippel для полиномиальной проверки идентичности быть derandomized ?
• Допускает ли линейное программирование алгоритм с сильно полиномиальным временем? (Это проблема № 9 в списке проблем Смейла .)
• Сколько запросов требуется, чтобы разрезать торт без зависти ?
• Каков алгоритм поисковой таблицы, которая последовательно генерирует игровые лабиринты в игре Entombed для Atari 2600 1982 года, просто исходя из значений пяти пикселей, смежных со следующими, которые должны быть сгенерированы?
• Какова алгоритмическая сложность задачи о минимальном остовном дереве ? Какова же сложность дерева решений проблемы MST? Оптимальный алгоритм для вычисления MST известен , но он основан на деревьях решений, поэтому его сложность неизвестна.

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

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

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

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

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

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

использованная литература

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

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