Последствия #P = FP

Каковы будут последствия #P = FP?

Меня интересуют как практические, так и теоретические последствия.

С практической точки зрения меня особенно интересуют последствия для искусственного интеллекта.

Указатели на бумаги или книги более чем приветствуются.

Пожалуйста, не говорите, что #P = FP подразумевает P = NP, я это уже знаю. Также, пожалуйста, не говорите: «Практических последствий не будет, если алгоритм будет работать во времени , где - количество электронов во Вселенной» $\Omega(n^{\alpha})$ $\alpha$ : позвольте мне предположить, что если существует детерминированный полиномиальный алгоритм времени для задачи с # P-полнотой, его время выполнения будет "clement" (например, ). $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Джорджо Камерани
источник

Ответы:

Вот несколько теоретических следствий равенства FP = # P, хотя они не имеют ничего общего с искусственным интеллектом. Предположение FP = # P эквивалентно P = PP , поэтому позвольте мне использовать последнее обозначение.

Если P = PP, то P = BQP : квантовое вычисление за полиномиальное время может быть смоделировано классическим детерминированным вычислением за полиномиальное время. Это является прямым следствием BQP⊆PP [ADH97, FR98] (и более раннего результата BQP⊆P ^PP [BV97]). Насколько мне известно, P = BQP, как известно, не следует из предположения P = NP. Эта ситуация отличается от случая рандомизированных вычислений ( BPP ): поскольку BPP⊆NP ^NP [Lau83], равенство P = BPP следует из P = NP.

Другое следствие P = PP состоит в том, что модель вычисления Блюма-Шуб-Смейла по вещественным числам с рациональными константами в определенном смысле эквивалентна машинам Тьюринга. Точнее, P = PP означает P = BP (P _ℝ⁰ ); то есть, если язык L ⊆ {0,1} ^* разрешим с помощью программы без констант по реалам за полиномиальное время, то L разрешим с помощью машины Тьюринга за полиномиальное время. (Здесь «BP» означает «логическая часть» и не имеет ничего общего с BPP.) Это следует из BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. См. Статью для определений. Важной проблемой в BP (P _ℝ⁰ ) является проблема суммы квадратови друзья (например, «Учитывая целое число k и конечный набор целочисленных координатных точек на плоскости, существует ли остовное дерево общей длины не более k ?») [Tiw92].

Аналогично второму аргументу, проблема вычисления конкретного бита в x ^y, когда положительные целые числа x и y заданы в двоичном виде, будет в P, если P = PP.

Ссылки

[ABKM09] Эрик Аллендер, Питер Бюргиссер, Йохан Кьельдгаард-Педерсен и Питер Бро Мильтерсен. По сложности численного анализа. SIAM Journal of Computing , 38 (5): 1987–2006, январь 2009 г. http://dx.doi.org/10.1137/070697926

[ADH97] Леонард М. Адлеман, Джонатан Де Маррай и Минг-Де А. Хуан. Квантовая вычислимость. Журнал SIAM по вычислительной технике , 26 (5): 1524–1540, октябрь 1997 г. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Итан Бернштейн и Умеш Вазирани. Квантовая теория сложности. Журнал SIAM по вычислительной технике , 26 (5): 1411–1473, октябрь 1997 г. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Лэнс Фортноу и Джон Роджерс. Ограничения сложности квантовых вычислений. Журнал компьютерных и системных наук , 59 (2): 240–252, октябрь 1999 г. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Клеменс Лаутеманн. BPP и полиномиальная иерархия времени. Письма для обработки информации , 17 (4): 215–217, ноябрь 1983 г. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Прасун Тивари. Проблема, которую легче решить на алгебраической оперативной памяти с удельной стоимостью. Журнал Сложности , 8 (4): 393–397, декабрь 1992 года. Http://dx.doi.org/10.1016/0885-064X(92)90003-T

Цуёси Ито
источник

Ты избил меня до этого! На самом деле, вы правы в отношении BQP против NP. Кажется, есть достаточные доказательства того, что BQP не содержится в PH (см., Например, arxiv.org/abs/0910.4698 ), хотя я считаю, что обобщенная гипотеза Линиала-Низана, которая используется во втором бите, с тех пор, как было показано, неверна.

Джо Фицсимонс

@turkistany: Если я не ошибаюсь, P = NP подразумевает P = BPP, потому что BPP содержится в PH, а если P = NP, то P = PH.

Ниль де Бодрап,

Между прочим: +1 для (FP = # P) ⇔ (P = PP), даже оставляя в стороне остальное содержание ответа.

Ниль де Бодрап

@Joe: В свете ответов на другой вопрос, я думаю, что лучшее доказательство «P = NP не подразумевает P = BQP» без фактического доказательства P = NP ≠ BQP, вероятно, будет результатом разделения оракула: «Существует оракул A такой, что P ^ A = NP ^ A ≠ BQP ^ A. ”Конечно, это совсем не просто, потому что этот результат подразумевает BQP ^ A⊈PH ^ A, что решает большой открытый вопрос.

Цуёси Ито

@Tsuyoshi: Разве вы не можете создать такого оракула из какого-либо оракула, относительно которого BQP не содержится в PH, просто взяв его вместе с PH, чтобы сформировать нового оракула?

Джо Фицсимонс

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

Суреш Венкат
источник

Тода доказал, что любая проблема в иерархии полиномиального времени может быть сведена к функции #P. Формально он доказал, что . Таким образом, если тогда рухнет, и, следовательно, у тавтологий будут короткие доказательства. $PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Мухаммед Аль-Туркистани
источник

Может кто-то уточнить: это не то же самое, что сказать «P = PH» (что сразу следует из P = NP)?

Ниль де Бодрап

@Niel: это не то же самое, это сильнее.

Джорджио Камерани

@ Вальтер: каким образом? Не является ли ? Если это так, то подразумевает .

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

Ниль де Бодрап

@All: просто чтобы уточнить --- мой первый комментарий выше задавал следующий вопрос "Является ли ответ туркистаны эквивалентным утверждению, что FP = # P подразумевает P = PH?" Если бы я хотел знать, эквивалентен ли FP = # P P = PH, я бы спросил об этом в комментарии к исходному сообщению, а не к ответу туркистани.

Ниль де Бодрап

@Niel: Ты прав. Это то же самое, что сказать P = PH, что следует из P = NP. Поэтому использование теоремы Тоды не было необходимости, поскольку FP = #P уже подразумевает P = NP = PH.

Робин Котари