Основные нерешенные проблемы в теоретической информатике?

Википедия перечислены только две проблемы под «нерешенных проблем в области информатики» :

• P = NP?
• Существование односторонних функций

Какие еще основные проблемы следует добавить в этот список?

Правила:

1. Только одна проблема в ответе
2. Предоставьте краткое описание и любые соответствующие ссылки

Можно ли умножить на матриц в операциях?n O ( n 2$n$$n$$O(n^2)$

Показатель самой известной верхней границы даже имеет специальный символ . В настоящее время составляет приблизительно 2.376 по алгоритму Копперсмита-Винограда . Хорошим обзором современного уровня является Сара Робинсон, « На пути к оптимальному алгоритму умножения матриц» , SIAM News, 38 (9), 2005.$\omega$$\omega$

Обновление: Эндрю Стотерс (в своей диссертации 2010 года ) показал, что , который был улучшен Вирджинией Васильевской Уильямс (в препринте в июле 2014 года ) до . Обе эти границы были получены путем тщательного анализа основной техники Копперсмита-Винограда.ω < $\omega < 2.3737$$\omega < 2.372873$

Дальнейшее обновление (30 января 2014 г.): Франсуа Ле Галль доказал, что в статье, опубликованной в ISSAC 2014 ( препринт arXiv ).$\omega < 2.3728639$

Изоморфизм графов в P?

Сложность графа изоморфизма (GI) была открытым вопросом в течение нескольких десятилетий. Стивен Кук упомянул это в своей статье 1971 года о NP-полноте SAT .

Определение того, являются ли два графика изоморфными, обычно можно быстро выполнить, например, с помощью таких программ, как nautyи saucy. С другой стороны, Миядзаки построил классы экземпляров, для которых nautyдоказуемо требуется экспоненциальное время.

Рид и Корнейл рассмотрели множество попыток справиться со сложностью ГИ до этого момента: болезнь изоморфизма графов , журнал теории графов 1 , 339–363, 1977.

GI, как известно, не находится в co-NP, но существует простой рандомизированный протокол для неизоморфизма графов (GNI). Поэтому считается, что GI (= co-GNI) «близок» к NP co-NP.${}\cap{}$

С другой стороны, если GI NP-полон, то полиномиальная иерархия разрушается. Так что GI вряд ли будет NP-завершенным. (Boppana, Håstad, Zachos. Имеет ли co-NP короткие интерактивные доказательства?, IPL 25 , 127–132, 1987)

Шива Кинтали хорошо обсуждает сложность GI в своем блоге.

Ласло Бабай доказал, что граф Изоморфизм находится в субэкспоненциальном времени .

Сложность Факторинга

Является ли факторинг в ?$\mathsf{P}$

• Последствия факторинга в П?
• Известны ли проблемы PRIMES, FACTORING как P-hard?
• Каковы последствия факторинга, являющегося NP-полным?
• Р с целочисленной факторизацией оракула
• Доказательства для целочисленной факторизации в P (на МО )

P = BPP?

Существует ли правило поворота для симплексного алгоритма, которое выдает наихудший случай времени полинома? В более широком смысле, существует ли сильно полиномиальный алгоритм для линейного программирования?

Гипотеза об экспоненциальном времени (ETH) утверждает, что для решения SAT требуется экспоненциальное время 2 ^{Ω (n)} . ETH подразумевает много вещей, например, что SAT отсутствует в P, поэтому ETH подразумевает P ≠ NP. См. Impagliazzo, Paturi, Zane, Какие проблемы имеют сильно экспоненциальную сложность? , JCSS 63, 512–530, 2001.

ETH широко распространено мнение, но, вероятно, будет трудно доказать, так как оно подразумевает много других разделений классов сложности.

Иммерман и Варди показывают, что логика с фиксированной точкой захватывает PTIME в классе упорядоченных структур. Одна из самых больших открытых проблем в теории описательной сложности состоит в том, может ли быть удалена зависимость от порядка:

Есть ли логика, которая фиксирует PTIME?

Проще говоря, логика захвата PTIME - это язык программирования для задач с графами, который работает непосредственно над структурой графов и не имеет доступа к кодированию вершин и ребер, так что выполняется следующее:

1. любая синтаксически правильная программа моделирует задачу вычислимого графа за полиномиальное время и
2. любая проблема вычислимого графа за полиномиальное время может быть смоделирована синтаксически правильной программой.

Если нет логики, которая захватывает PTIME, то так как NP захватывается экзистенциальной логикой второго порядка. Логика захвата PTIME обеспечит возможную атаку на P против NP.$P \neq NP$

См. Неформальную дискуссию в блоге Липтона, а М. Гроше: в поисках логического захвата PTIME (LICS 2008) для более технического обследования.

Верна ли гипотеза об уникальных играх ?
И: Учитывая, что для Уникальных Игр существуют субэкспоненциальные алгоритмы аппроксимации по времени , где проблема в конечном итоге лежит в плане сложности?

Постоянный против детерминанта

Постоянный и детерминантный вопрос интересен из-за двух фактов. Во-первых, перманент матрицы подсчитывает количество совершенных совпадений в двудольном графе. Следовательно, перманент такой матрицы # P-Complete. В то же время определение перманента очень близко к определению детерминанта, и в конечном итоге оно отличается только из-за простого изменения знака. Общеизвестно, что детерминантные вычисления приведены в P. Изучение различий между перманентом и детерминантом и того, сколько вычислений детерминанта требуется для вычисления перманента, говорят о P по сравнению с #P.

Можем ли мы вычислить БПФ за намного меньшее, чем время?$O(n \log n)$

В том же (очень) общем ключе есть много вопросов по улучшению времени выполнения многих классических задач или алгоритмов: например, можно ли решить все пары по кратчайшим путям (APSP) в время?$O(n^{3-\epsilon})$

Изменить: APSP выполняется во времени ", где добавления и сравнения реалов являются удельной стоимостью (но все другие операции имеют типичные логарифмическая стоимость) ": http://arxiv.org/pdf/1312.6680v2.pdf$(\frac{n^3}{2^{\Omega(log n)^{1/2}}})$

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

Или в более общем плане: является ли любое динамическое двоичное дерево поиска O (1) онлайн-конкурентным?

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

NP против со-NP

Вопрос NP против co-NP интересен, потому что NP ≠ co-NP подразумевает P ≠ NP (так как P замкнуто относительно дополнения). Это также относится к «двойственности»: разделение между поиском / проверкой примеров и поиском / проверкой контрпримеров. Фактически, доказательство того, что вопрос находится как в NP, так и в совместном NP, является нашим первым хорошим доказательством того, что проблема, которая, кажется, находится за пределами P, также, вероятно, не является NP-Complete.

Существуют ли проблемы, которые не могут быть эффективно решены с помощью параллельных компьютеров?

Проблемы, которые являются P-полными, не известны как распараллеливаемые. P-complete проблемы включают Horn-SAT и линейное программирование. Но доказательство того, что это так, потребует отделения некоторого понятия распараллеливаемых задач (таких как NC или LOGCFL) от P.

Конструкции компьютерных процессоров увеличивают количество процессоров, в надежде, что это приведет к повышению производительности. Если фундаментальные алгоритмы, такие как линейное программирование, по своей сути не распараллеливаются, то это имеет существенные последствия.

У всех ли пропозициональных тавтологий есть доказательства Фреге полиномиального размера?

Возможно, главная открытая проблема сложности доказательств : продемонстрировать нижние оценки суперполиномиального размера на пропозициональных доказательствах (называемых также доказательствами Фреге).

Неформально система доказательств Фреге - это просто стандартная система пропозициональных доказательств для доказательства пропозициональных тавтологий (каждый учится на базовом курсе логики), имеющая аксиомы и правила вывода, где линии доказательства записываются в виде формул. Размером из доказательства Фрега является количеством символов , он принимает , чтобы записать доказательство.

Проблема тогда спрашивает , есть ли семья пропозициональных тавтологических формул , для которых нет полинома таким образом, что минимальный Фрег доказательства размера не превосходит , для всех (где обозначает размер формулы ).$(F_n)_{n=1}^\infty$$p$$F_n$$p(|F_n|)$$n=1,2,\ldots$$|F_n|$$F_n$

Формальное определение системы доказательства Фреге

Определение (правило Фреге) Правило Фреге - это последовательность пропозициональных формул для , записанная как . В случае правило Фреге называется аксиомной схемой . Формула называется производной по правилу от если - все экземпляры подстановки , для некоторого назначения переменным (то есть есть формулы $A_0(\overline x),\ldots,A_k(\overline x)$$k \le 0$$\frac{A_1(\overline x), \ldots,A_k(\overline x)}{A_0(\overline x)}$$k = 0$$F_0$$F_1,\ldots,F_k$$F_0,\ldots,F_k$$A_1,\ldots,A_k$$\overline x$$B_1,\ldots,B_n$ такой, что для всех . Правило Фреге считается обоснованным, если всякий раз, когда присвоение удовлетворяет формулам в верхней части , то оно также удовлетворяет формуле в нижней части .$F_i = A_i(B_1/x_1,\ldots,B_n/x_n),$$i=0,\ldots,k$$A_1,\ldots,A_k$$A_0$

Определение (доказательство Фреге). При заданном наборе правил Фреге доказательство Фреге представляет собой последовательность формул, в которой каждая линия доказательства является либо аксиомой, либо была получена по одному из данных правил Фреге из предыдущих линий доказательства. Если последовательность заканчивается формулой , то доказательство , как говорят, является доказательством . Размером из доказательства Фрега является общим размером всех формул в доказательстве.$A$$A$

Доказательство система называется implicationally полным , если для всех набора формул , если семантически означает , то есть доказательство с помощью (возможно) аксиомы из . Система доказательств называется надежной, если она допускает доказательства только тавтологий (когда не используются вспомогательные аксиомы, как в выше).$T$$T$$F$$F$$T$$T$

Определение (система доказательств Фреге). Учитывая язык высказываний и конечное множество нормальных правил Фреге, мы говорим, что - система доказательств Фреге, если импликационно полон.$P$$P$$P$

Обратите внимание, что доказательство Фреге всегда обоснованно, поскольку правила Фреге считаются надежными. Нам не нужно работать с конкретной системой доказательства Фреге, поскольку базовый результат в сложности доказательства утверждает, что каждые две системы доказательства Фреге, даже на разных языках, являются полиномиально эквивалентными [Reckhow, кандидатская диссертация, Университет Торонто, 1976].

Установление нижних оценок доказательств Фреге можно рассматривать как шаг к доказательству , поскольку, если это так, то ни одна система пропозициональных доказательств (включая Фреге) не может иметь полиномиальных доказательств размера для всех тавтологий.$NP \neq coNP$

Можем ли мы вычислить расстояние редактирования между двумя строками длины за субквадратичное время, то есть за время для некоторого ?$n$$O(n^{2-\epsilon})$$\epsilon>0$

Существуют ли действительно субквадратичные алгоритмы времени (то есть времени для некоторой константы ) для 3SUM-сложных задач ?$O(n^{2-\delta})$$\delta>0$

В 2014 году Грёнлунд и Петти описали детерминистический алгоритм для самого 3SUM, который работает за время . Хотя это основной результат, улучшение по сравнению с является только (суб) логарифмическим. Более того, аналогичные субквадратичные алгоритмы не известны для большинства других 3SUM-сложных задач.О ( п 2$O(n^2/(\log n/\log \log n)^{2/3})$$O(n^2)$

BQP = P?

Также: NP содержится в BQP?

Я знаю, что это нарушило правила, имея в ответе два вопроса, но когда они взяты вместе с вопросом P против NP, они не обязательно являются независимыми вопросами.

1. Гипотеза об изоморфизме. (Являются ли все NP-полные проблемы «одной и той же» проблемой?)
2. Может ли криптография основываться на NP-полной проблеме?

и немного дальше от основного направления:


3. Каков размер NP в EXP?

(Неофициально, если у вас есть все проблемы в EXP на столе, и вы случайно выбираете один случайным образом, какова вероятность того, что выбранная вами проблема также есть в NP? Этот вопрос был формализован понятием меры, ограниченной ресурсами Известно, что P имеет нулевой показатель в EXP, т. Е. Проблема, которую вы выбрали из таблицы, почти наверняка не в P.)

Какова приближенность метрической TSP ? Алгоритм Кристофидеса 1975 года является алгоритмом аппроксимации полиномиального времени (3/2). NP-трудно сделать лучше?

• Приближение показателя TSP к показателям с коэффициентом меньше 220/219 является NP-сложным (Papadimitriou and Vempala, 2006 [PS] ). Насколько мне известно, это самая известная нижняя граница.

• Есть некоторые свидетельства того, что фактическая граница может быть 4/3 (Carr and Vempala, 2004 [Бесплатная версия] [Хорошая версия] ).

• Верхняя граница аппроксимируемости была недавно снижена до (Mucha 2011 "13/9 -приложение для графического TSP" [ PDF ])$13/9$

Дайте явную функцию с показательной сложностью схемы.

Шеннон доказал в 1949 году, что если вы случайно выберете булеву функцию, она будет иметь экспоненциальную сложность схемы с вероятностью, почти равной единице.

Лучшая нижняя граница для явной булевой функции мы имеем до сих пор, равна К. Ивамы, О. Лахиша, H Морицуми и Р. Раз.5 n - o ( n $f:\{0,1\}^n \to \{0,1\}$$5n - o(n)$

Какова сложность запроса тестирования свободы от треугольников в плотных графах (т. Е. Отличать графы без треугольников от этих -far от свобод от треугольников)? Известная верхняя граница представляет собой башню экспонент в , в то время как известная нижняя граница является лишь слегка суперполиномиальной в . Это довольно простой вопрос в теории экстремальных графов / аддитивной комбинаторике, который был открыт в течение почти 30 лет.1 / ϵ 1 /$\epsilon$$1/\epsilon$$1/\epsilon$

Отдельный NEXP от BPP. Люди склонны верить, что BPP = P, но никто не может отделить NEXP от BPP.

Я знаю, что ОП запрашивал только одну проблему на пост, но конференции RTA (методы переписывания и их приложения) 1 и TLCA (типизированные лямбда-исчисления и их приложения) поддерживают списки открытых проблем в своих областях 2 . Эти списки весьма полезны, так как они также включают указатели на предыдущую работу, проделанную для решения этих проблем.

Дерандомизация задачи проверки полиномиальной идентичности

Проблема заключается в следующем: для заданной арифметической схемы, вычисляющей многочлен , тождественно ли равен нулю?$P$$P$

Эта проблема может быть решена за рандомизированное полиномиальное время, но неизвестно, что она разрешима за детерминированный полиномиальное время.

С этим связана гипотеза Шуба и Смейла . Для заданного полинома мы определяем его сложность как размер наименьшей арифметической схемы, вычисляющей с использованием единственной константы . Для одномерного многочлена пусть - его число действительных корней.P τ τ ( P ) P 1 P ∈ Z [ x ] z ( P $\tau$$P$$\tau$$\tau(P)$$P$$1$$P\in\mathbb Z[x]$$z(P)$

Докажите, что существует универсальная постоянная такая, что для любого , .$c$$P\in\mathbb Z[x]$$z(P)\le (1+\tau(P))^c$

Есть ли квантовая теорема PCP?

В лямбда-исчислениях много открытых проблем (типизированных и нетипизированных). См. Список открытых проблем TLCA для деталей; также есть хорошая версия PDF без рамок.

Мне особенно нравится проблема № 5:

Есть ли в неиспользуемые но с помощью положительных рекурсивных типов?$F_ω$

Является ли проблема дискретного логарифма в P?

Пусть циклическая группа порядка и такая , что является генератором . Проблема нахождения такой, что , известна как проблема дискретного логарифма (DLP). Существует ли (классический) алгоритм для решения DLP в наихудшем полиномиальном времени по числу битов ?q g , h ∈ G g G n ∈ N g n = h $G$$q$$g,h \in G$$g$$G$$n \in \mathbb{N}$$g^n = h$$q$

Существуют варианты DLP, которые считаются более простыми, но все еще не решены. Вычислительная задача Диффи-Хеллмана (ЦРБ) запрашивает для нахождения данную и . Принятия решения проблем Диффи-Хеллмана (ДДГ) просит решающем, учитывая , если . g , g a g b g , g a , g b , h ∈ G g a b = $g^{a b}$$g, g^a$$g^b$$g, g^a, g^b, h \in G$$g^{a b} = h$

Очевидно, что DLP сложно, если CDH сложно, и CDH трудно, если DDH сложно, но обратные сокращения не известны, за исключением некоторых групп. Предположение, что DDH сложен, является ключом к безопасности некоторых криптосистем, таких как ElGamal и Cramer-Shoup .

Игры с четностью - это графические игры для двух игроков с бесконечной продолжительностью, естественная проблема решения которых в NP и co-NP, а также естественная проблема поиска в PPAD и PLS.

http://en.wikipedia.org/wiki/Parity_game

Можно ли решить паритетные игры за полиномиальное время?

(В целом, давний главный открытый вопрос в математическом программировании заключается в том, могут ли P-матричные линейные задачи дополнительности быть решены за полиномиальное время?)

Область параметризованной сложности имеет свою собственную нагрузку на открытые проблемы.

Рассмотрим решение проблемы

• при заданном существует ли покрытие вершин размера для графа ?$(G,k)$$k$$G$
• При заданном существует ли удовлетворительное распределение веса для формулы ?$(F,k)$$k$$F$
• при заданном существует ли клика размера в графе ?$(G,k)$$k$$G$
• и т.д...

Многие, многие, комбинаторные проблемы существуют в этой форме. Параметризованная сложность рассматривает алгоритм как «эффективный», если его время выполнения ограничено сверху где - произвольная функция, а - постоянная, не зависящая от . Для сравнения отметим, что все такие проблемы легко решаются в .$f(k)n^c$$f$$c$$k$$n^{O(k)}$

Эта структура моделирует случаи, в которых мы ищем небольшую комбинаторную структуру, и мы можем предоставить экспоненциальное время выполнения по отношению к размеру решения / свидетеля .

Проблема с таким алгоритмом (например, покрытие вершины) называется « Исправляемый параметр с возможностью изменения параметров» (FPT).

Параметризованная сложность является зрелой теорией и имеет как сильные теоретические основы, так и привлекательность для практического применения. Задачи решения, интересные для такой теории, образуют очень хорошо структурированную иерархию классов с естественными полными задачами:

Конечно, это открыто, если любое из таких включений строгое или нет. Обратите внимание, что если то SAT имеет субэкспоненциальный алгоритм (это не тривиально). Последнее утверждение связывает прамеризированную сложность с упомянутым выше.E T $FPT=W[1]$$ETH$

Также обратите внимание, что исследование таких коллапсов не является пустым упражнением: доказательство того, что эквивалентно доказательству наличия алгоритма с фиксированным параметром для поиска -кликов.$W[1]=FPT$$k$