Открытые проблемы на границах ТКС

В теме Основные нерешенные проблемы теоретической информатики? Иддо Цамерет сделал следующий превосходный комментарий:

Я думаю, что мы должны различать основные открытые проблемы, которые рассматриваются как фундаментальные проблемы, такие как $P\neq NP$ , и основные открытые проблемы, которые в случае решения будут представлять собой технический прорыв, но не обязательно такие фундаментальные, например, экспоненциальные нижние оценки для $AC^0(6)$ цепей (то есть вентилей). Поэтому нам, возможно, следует открыть новую вики сообщества под названием «Открытые проблемы на границах TCS» или тому подобное.$AC^0+\mod 6$

Поскольку Iddo не запускал тему, я подумал, что я начну эту тему.

Часто основные открытые проблемы полей известны исследователям, работающим в смежных областях, но точка, в которой застряли нынешние исследования, посторонним неизвестна. Приведенный пример хороший. Как сторонний наблюдатель, ясно, что одна из самых больших проблем в сложности цепей - показать, что NP требует цепей суперполиномиального размера. Но посторонние могут не знать, что текущая точка, в которой мы застряли, пытается доказать экспоненциально нижние границы для цепей AC ⁰ с вентилями mod 6. (Конечно, могут быть и другие проблемы сложности схемы аналогичной сложности, которые описывают, где мы застряли. Это не уникально.) Другой пример - показать нижние границы пространства-времени для SAT лучше, чем n ^1.801 .

Эта тема для примеров, подобных этому. Поскольку такие проблемы трудно охарактеризовать, я просто приведу несколько примеров свойств, которыми обладают такие проблемы:

1. Часто не будет больших открытых проблем области, но будет большим прорывом, если решится.
2. Обычно это не невероятно сложно, в том смысле, что если бы кто-то сказал вам, что проблема была решена вчера, в это не будет слишком трудно поверить.
3. Эти проблемы также часто имеют числа или константы, которые не являются фундаментальными, но они возникают, потому что это происходит там, где мы застряли.
4. Проблема на границах определенной области будет время от времени меняться, в отличие от самой большой проблемы в этой области, которая останется неизменной на протяжении многих лет.
5. Часто эти проблемы являются самыми легкими проблемами, которые все еще открыты. Например, у нас также нет экспоненциальных нижних границ для AC ¹ , но, поскольку [6] включен в этот класс, формально легче показать нижние оценки для [6], и, таким образом, это в текущая граница сложности схемы. A C $AC^0$$AC^0$

Пожалуйста, разместите один пример за ответ; применяются стандартные соглашения о биг-листе и CW. Если кто-то может объяснить, какие типы проблем мы ищем лучше, чем у меня, пожалуйста, не стесняйтесь редактировать этот пост и вносить соответствующие изменения.

РЕДАКТИРОВАТЬ: Каве предположил, что ответы также включают в себя объяснение того, почему данная проблема находится на границе. Например, почему мы ищем нижние оценки для AC ⁰ [6], а не для AC ⁰ [3]? Ответ в том, что у нас есть более низкие оценки для AC ⁰ [3]. Но тогда очевидный вопрос состоит в том, почему эти методы терпят неудачу для AC ⁰ [6]. Было бы неплохо, если бы ответы тоже могли это объяснить.

Вот три кратчайших пути исследования:

O ( n + m log w ) 2 $1$ . Существует ли линейный алгоритм времени для кратчайших путей с одним источником в ориентированных графах с неотрицательными весами, по крайней мере, в модели вычисления слово-RAM? Обратите внимание, что для неориентированных графов существует линейный алгоритм времени (см. Статью Торупа). Исходя из этого, Hagerup имеет время выполнения для ориентированных графов с весами, ограниченными . Есть ли более быстрый алгоритм?$O(n+m\log w)$$2^w$

O ( n ω n ) ω < 2,337 O ( n 2,575 ) O ( n ω n $2$ . Существует ли алгоритм polylog для всех пар кратчайших путей в невзвешенных ориентированных графах? ( - это показатель умножения матриц). Текущее лучшее время выполнения - это по , и для неориентированных графов эту проблему можно решить в polylog .$O(n^\omega$$n)$$\omega<2.376$$O(n^{2.575})$$O(n^\omega$$n)$

(Направленные проблемы на самом деле сложнее?)

O ( n 2,9 ) n 0 , … , $3$ . Существует ли алгоритм для всех пар кратчайших путей в графах с узлами с весами в { }? Или есть сокращение от общей проблемы кратчайших путей всех пар к этому ограничению?$O(n^{2.9})$$n$$0,\ldots,n$

Это уже упоминалось в вопросе:

Открыто:

Отделите от ( контуров глубины 2). A C 0 2 [ 6 ] A C 0 [ 6 $EXP^{NP}$$AC^0_2[6]$$AC^0[6]$(см. обновление ниже)

[Ноябрь 11, 2010] Отдельный от . Отдельный от .A C 0 2 [ 6 ] E X P N P T C $EXP$$AC^0_2[6]$$EXP^{NP}$$TC^0$

Известен:

1. [Александр Разборов 1987 - Роман Смоленский 1987] отсутствует в если простое число, а не степень . A C 0 [ p k ] p m $MOD_m$$AC^0[p^k]$$p$$m$$p$

2. [Arkadev Chattopadhyay и Avi Wigderson 2009] Пусть m, q - взаимно простые числа, такие что m не имеет квадратов и имеет не более двух простых факторов. Пусть C - любая схема типа где - либо либо а на базе имеют произвольные принимающие множества. Если C вычисляет то верхний и, следовательно, размер схемы должны быть . G Н Д О Р М О Д м М О Д д 2 Ω ( п $MAJoGoMOD^A_m$$G$$AND$$OR$$MOD_m$$MOD_q$$2^{{\Omega(n)}}$

Более поздний результат основан на получении экспоненциально малой границы функции с подсхемами глубины 2 и оценке экспоненциальных сумм, включающих полиномы низкой степени.$MOD_q$

Препятствия:

Обновление [ноябрь 10, 2010]

Бумаги по Райан Уильямс , похоже, решили эту открытую проблему , используя методы , которые кажутся существенно отличаются от тех , которые упомянуты выше:

[Райан Уильямс 2010] не имеет неоднородных цепей размером . A C C 0 2 n o ( 1 $E^{NP}$$ACC^0$$2^{n^{o(1)}}$

Рекомендации:

• А.А. Разборов. Нижние оценки размеров ограниченных глубинных сетей по полному базису с логическим сложением (на русском), в Математические заметки, 41 (4): 598–607, 1987. Английский перевод в математических заметках Академии наук СССР, 41 (4): 333–338, 1987.

• Р. Смоленский. Алгебраические методы в теории нижних оценок сложности булевой схемы. В STOC, страницы 77–82. ACM, 1987.

• Аркадьев Чаттопадхяй и Ави Вигдерсон. Линейные системы над составными модулями, FOCS 2009

• Райан Уильямс. Неравномерная схема ACC Нижние границы , 2010 г., черновик (представлен?).

Пусть CNF-SAT будет проблемой определения того, является ли данная формула CNF выполнимой (без ограничений по ширине предложений).

Разрешается ли CNF-SAT для переменных и предложений за времени для некоторого ?m 2 δ n p o l y ( m ) δ < $n$$m$$2^{\delta n} poly(m)$$\delta < 1$

Это хорошо известная открытая проблема в области «более быстрых алгоритмов для NP». Я не думаю, что она достигла статуса «крупной открытой проблемы», но привлекла немало внимания. Самые известные алгоритмы запускаются за времени (например, здесь ).$2^{n-\Omega(n/\log (m/n))}$

Относительно гипотезы об экспоненциальном времени (что 3SAT не находится в субэкспоненциальном времени), существует также «гипотеза сильного экспоненциального времени» , согласно которой оптимальное время выполнения для -SAT сходится к как . Одним из следствий Strong-ETH будет то, что ответ на поставленный выше вопрос - нет. Несколько правдоподобных гипотез подразумевают, что ответ - да , но кто знает.2 n k → $k$$2^{n}$$k \rightarrow \infty$

Я думаю, что это одна из тех проблем, которые, похоже, могут быть «решены» в любом случае: либо мы покажем ответ «да», либо покажем, что ответ «да» подразумевает нечто очень важное. В первом случае мы получим удовлетворение от решения проблемы, во втором случае мы повысим вопрос до вопроса "крупной открытой проблемы" ... отсутствие ответа подразумевает , и да-ответ подразумевает что-то очень важное. :)$P \neq NP$

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

ОТКРЫТЫЙ

Являются ли PAC деревьев решений (DT) обучаемыми при равномерном распределении на примерах (или вообще)?

ИЗВЕСТЕН

• DT не могут быть изучены при равномерном распределении со статистическими запросами (SQ) [ Blum et al. '94 ]
• случайные DT могут быть изучены при равномерном распределении [ Джексон, Servedio '05 ]
• монотонные DT могут быть изучены при равномерном распределении [ O'Donnell, Servedio '06 ]
• сглаженный анализ для обучения ДЦ при равномерном распределении [ Kalai, Teng '08 ]

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

Эта проблема также, похоже, решается со всех сторон. Мы знаем, что при равномерном распределении по примерам: монотонные деревья решений могут быть изучены, что случайные деревья решений могут быть изучены, и что существует также сглаженный анализ. Мы также знаем, что алгоритм SQ не решит эту проблему. И в этой области также наблюдается устойчивый прогресс. С другой стороны, это сложная проблема, которая была открыта некоторое время, так что, похоже, она отвечает требованиям "Открытых проблем на границах TCS".

Обратите внимание, что есть и другие результаты, в которых я не принимал во внимание сложность правильного обучения DT, способность изучать DT с помощью запросов и сложность изучения даже случайных DT с SQ.

ОТКРЫТЫЙ:

Показать нижнюю границу в модели зондирования ячейки для явной статической проблемы со структурами данных, которая доказывает, что при некотором «разумном» ограничении пространства (например, пространство является полиномиальным по размеру входных данных), тогда время запроса должно быть равным наименьший T, где T больше, чем log | Q |, где Q - множество запросов. Это называется «log | Q | -барьером» (или иногда, несколько ошибочно, «logn-барьером»).

ИЗВЕСТЕН:

1. нижние оценки выше log | Q | для неявной проблемы (см . опрос Мильтерсена )

2. нижние оценки выше log | Q | с экстремальными ограничениями пространства (например, краткие нижние границы)

3. нижние оценки выше log | Q | для динамических задач (где я имею в виду, что если время обновления очень мало, то время запроса должно быть очень большим, или наоборот; см., например, нижнюю границу Патраску для частичной суммы)

4. Нижние границы в ограниченных моделях, таких как указатели, модели сравнения и т. Д.

5. нижние оценки, ломающие лог | Q | Барьер не может быть доказан стандартным видом уменьшения сложности связи, потому что Алиса может просто отправить сам запрос, который принимает только log | Q | биты, и поэтому легко проверить, что сокращение никогда не даст лучшую нижнюю границу, чем эта. Таким образом, должен использоваться либо «родной» для модели зондирования ячейки, либо должно использоваться более умное уменьшение сложности связи.

В низкоуровневых классах сложности есть интересная проблема с характеристикой .$\mathsf{NL}$

ОТКРЫТЫЙ:

Покажите, что равно .U $\mathsf{NL}$$\mathsf{UL}$

N $\mathsf{UL}$ , однозначное пространство журналов , - это класс, состоящий из задач, которые могут быть решены с помощью -машины с дополнительным ограничением, что существует не более одного приемлемого пути вычисления.$\mathsf{NL}$

ИЗВЕСТЕН:

• В неоднородных обстоятельствах . [RA00]$\mathsf{NL/poly} = \mathsf{UL/poly}$
• При вероятных допущениях твердости ( требует схем экспоненциального размера), результат [RA00] можно дерандомизировать, чтобы показать, что . [ARZ99]N L = U $\mathsf{SPACE}(n)$$\mathsf{NL} = \mathsf{UL}$
• Достижимость на 3-страничных графиках завершена для . [PTV10]$\mathsf{NL}$
• Достижимость на 2-страничных графиках разрешима для . [BTV09]$\mathsf{UL}$
• Если , то . [AJ93]$\mathsf{NL} = \mathsf{UL}$$\mathsf{FNL} \subseteq \mathsf{\sharp L}$

НЕИЗВЕСТНЫЙ:

• Промежуточный класс , который определен как задачи, решаемые машиной с максимально полиномиально большим количеством приемлемых путей вычислений, находится между и . Никаких обвалов не известно.$\mathsf{FewL}$$\mathsf{NL}$$\mathsf{NL}$$\mathsf{UL}$
• Известно, что по известной теореме Иммермана-Селецкеньи, в то время как замкнуто относительно дополнения, все еще открыто.$\mathsf{NL} = \mathsf{coNL}$$\mathsf{UL}$

Некоторые открытые проблемы PCP:

• Гипотеза скользящей шкалы. В PCP мы хотим, чтобы ошибка верификатора была как можно меньше. BGLR предположил, что ошибка может доходить до где - случайность (ясно, что нижняя граница ). Цена, которую вы платите за уменьшение ошибки - это только правильное увеличение алфавита.$2^{-\Theta(r)}$$r$$2^{-r}$

Более формально: гипотеза состоит в том, что существует переменная переменного тока, такая что для всех натуральных r, для всех , существует верификатор PCP, который использует случайность r, чтобы сделать два запроса для доказательства, имеет совершенный ошибка в полноте и обоснованности . Алфавит доказательства зависит только от .$\varepsilon \geq 2^{-cr}$$\varepsilon$$1/\varepsilon$

Для двух запросов самая известная ошибка - для некоторого конкретного (M-Raz, 2008). Можно также получить ошибку для любого , с количеством запросов, зависящих от (DFKRS).$1/r^{\beta}$$\beta>0$$2^{-r^{\alpha}}$$\alpha <1$$\alpha$

Нижние оценки на c (то есть алгоритмы приближения) также ищутся.

См . Опрос Ирит Динур для более подробной информации.

• Линейная длина PCP. Существуют коды исправления ошибок большого расстояния с линейной длиной. Есть ли PCP с линейной длиной?

В частности, нам нужен верификатор для выполнения формулы SAT, которая имеет постоянное количество запросов, постоянный алфавит и постоянную ошибку, и получает доступ к доказательству длины, линейной по длине формулы? Это открыто даже для ошибки, близкой к 1 (но лучше, чем тривиальный ), субэкспоненциального алфавита и сублинейного числа запросов.$1-1/n$

Самая известная длина - для постоянной ошибки и для субконстантной ошибки.$n polylog n$$n \cdot 2^{(log n)^{1-\beta}}$

Докажите, что для каждого в , который не имеет (неоднородных) цепей с проводами . Напомним, что . То есть, доказать экспоненциальное время нижних границ суперлинейного контура с доступом к оракулу .$c > 0$$E^{NP}$$c n$$E = \bigcup_{k \geq 1} TIME[2^{k n}]$$NP$

-локально декодируемыми код (НРС) является отображением такое , что существует алгоритм , называемый локальный декодер , который, учитывая в качестве входных данных целое число и полученное слово которое отличается от для некоторого не более доля позиций, ищет не более координат и выдает с вероятностью не менее . НРС называется линейной, если$(q,\delta,\epsilon)$$C: \mathbb{F}^m \to \mathbb{F}^n$$A$$i \in [m]$$y \in \mathbb{F}^n$$C(x)$$x \in \mathbb{F}^m$$\delta$$q$$y$$x_i$$1/|\mathbb{F}| + \epsilon$$\mathbb{F}$является полем и является -линейного. НРС имеют множество приложений в теории сложности и конфиденциальности, среди других.$C$$\mathbb{F}$

Для и константы ситуация полностью разрешена. Код Адамара представляет собой линейный запросный LDC с , и это, как известно, является по существу оптимальным, даже для нелинейных LDC. Но здесь является границей! Как только мы сделаем , между известными верхними и нижними границами будет огромный разрыв. Наилучшая текущая верхняя граница - это линейный запросный LDC над любым конечным полем (и даже действительными и комплексными) со сложностью запроса [ Ефременко '09 , Двир-Гопалан-Еханин '10 ]. Лучшие нижние оценки$q=2$2 п = ехр ( т ) д = 2 д = 3 3 п = ехр ( ехр ( $\delta,\epsilon$$2$$n = \exp(m)$$q=2$$q=3$$3$$n=\exp(\exp(\sqrt{\log m \log \log m})) = 2^{m^{o(1)}}$$\Omega(m^2)$ для линейных запросов НРС над любым полем и для общих запросов НРС [ Вудрафф '10 ]. Ситуация с большим количеством запросов еще более ужасна.$3$$\Omega(m^2/\log m)$$3$

Каков наибольший возможный разрыв между детерминистскими и (2-сторонними сложностями квантовых запросов) сложными функциями?

Открыто:

Существует ли полная функция, сложность квантового запроса которой равна T, а детерминированная сложность запроса равна ω (T ² )?

Существует ли полная функция, сложность квантового запроса которой равна T, а детерминированная сложность запроса равна ω (T ⁴ )?

Если полная функция может быть вычислена с помощью T запросов с помощью квантового алгоритма, всегда ли она может быть вычислена с помощью запросов с помощью детерминированного алгоритма?$o(T^6)$

Известен:

Если сложность квантового запроса для полной функции равна T, то сложность ее детерминированного запроса равна . (Ссылка)$O(T^6)$

Самый большой известный разрыв достигается с помощью функции ИЛИ, которая достигает квадратичного разрыва.

Обновление (21 июня 2015 г.) : теперь мы знаем функцию, которая обеспечивает разделение на четыре части (четвертая степень). См. Http://arxiv.org/abs/1506.04719 .

Предполагается, что функция ИЛИ достигает максимально возможного разрыва.

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

Открыто:

Существует ли полная функция, точная квантовая сложность запроса которой равна T, а детерминированная сложность запроса равна ?$\omega(T)$

Известен:

Если точная квантовая сложность запроса для полной функции равна T, то ее детерминированная сложность запроса равна . (Ссылка)$O(T^3)$

Самый известный разрыв - это коэффициент 2.

Обновление (5 ноября 2012 г.) : Это было улучшено в суперлинейном преимуществе для точных квантовых алгоритмов Андрисом Амбайнисом . Из аннотации: «Мы представляем первый пример булевой функции f (x_1, ..., x_N), для которой точные квантовые алгоритмы имеют суперлинейное преимущество над детерминированными алгоритмами. Любой детерминированный алгоритм, который вычисляет нашу функцию, должен использовать N запросов, но Точный квантовый алгоритм может вычислить его с помощью O (N ^ {0.8675 ...}) запросов. "

Существует ряд открытых проблем, связанных со сложностью доказательства, я упомяну только одну, которая остается открытой даже после того, как некоторые эксперты потратили годы на ее решение. Это доказательная сложность версии состояния в сложности схемы. (См. [Segerlind07], если вы хотите увидеть больше открытых проблем в сложности доказательства.)

открыто

Докажите суперполиномиальные нижние оценки размера доказательства для системы доказательств -Frege.$AC^0[2]$

$AC^0[2]$ -Frege (он же d-Frege + ) - система доказательства предложения, которая допускает только схемы ( с вентилями).$CG_2$$AC^0[2]$$AC^0$$\bmod 2$

Известен

1. Для -Frege существует экспоненциальный размер доказательства (он же постоянная глубина Фреге, d-Фреге) для (пропозициональная формулировка принципа голубиных отверстий с голубями и отверстия). Существуют также экспоненциальные нижние границы для -Frege + (постоянная глубина Фреге с учетом аксиом ). Также известно, что -Frege + не ограничены полиномиально. P H P n + 1 n n + 1 n A C 0 C A p mod p A C 0 C A $AC^0$$PHP^{n+1}_{n}$$n+1$$n$$AC^0$$CA_p$$\bmod p$$AC^0$$CA_m$

2. Для соответствующего класса цепей, а именно существуют экспоненциальные нижние границы размера цепи .$AC^0[2]$

Рекомендации:

• Натан Сегерлинд, «Сложность пропозициональных доказательств», Бюллетень символической логики 13 (4), 2007

Открыто:

Показать разделение оракула между QIP (2) и AM. То есть, показать проблему в QIP (2) ^А , что не в AM ^A .

Большая открытая проблема состоит в том, чтобы показать разделение оракула между BQP и PH. Но у нас даже нет разделения между BQP и AM (поскольку AM находится в PH, это должно быть проще). Хуже того, сделайте BQP значительно более мощным, разрешив 1-раундовое взаимодействие с Мерлином, предоставив вам класс QAM или QIP (2) (в зависимости от публичных монет или частных монет), и у нас все еще нет разделения.

Известен:

Самое известное разделение - между BQP и MA, которое происходит из этой статьи Джона Уотроуса . Для классов сложности, которые не являются классами проблем решения, см. Эти результаты Скоттом Ааронсоном .

Я не уверен, относится ли это к классу пограничных открытых проблем или крупных открытых проблем, поэтому комментарии приветствуются.

Открыто:

Покажите, означает ли что рухнет или нет.P $\mathsf{NP} = \mathsf{UP}$$\mathsf{PH}$

$\mathsf{UP}$ ( однозначное полиномиальное время) - это класс, определенный как задачи решения, решаемые NP-машиной с дополнительным ограничением, которое

• на любом входе есть не более одного приемлемого пути вычисления.

Эта проблема была заявлена ​​в блоге сложности в 2003 году.

Известен:

Результат по Hemaspaandra, Найк, Ogiwara и Зельман показывает , что если имеет место следующее утверждение, то многочлен иерархия падает на второй уровень.

• Существует язык такое , что для каждой формулы в SAT, есть уникальное удовлетворяющее задание с в . L ϕ x ( ϕ , x ) $\mathsf{NP}$$L$$\phi$$x$$(\phi,x)$$L$

Неизвестный:

Любые маловероятные разрушения или разлуки.

Связанный пост: Больше о синтаксических против семантических классов, и UP против NP .