Любой многочлен, который трудно сосчитать, но легко решить?

15

Каждая монотонная арифметическая схема , то есть -цепь, вычисляет некоторый многомерный многочлен с неотрицательными целыми коэффициентами. Учитывая полином , схема{+,×}f ( x 1 , , x n )F(x1,,xn)f(x1,,xn)

  • вычисляет если выполняется для всех ; F ( a ) = f ( a ) a N nfF(a)=f(a)aNn
  • считает если выполняется для всех ; F ( a ) = f ( a ) a { 0 , 1 } nfF(a)=f(a)a{0,1}n
  • решает если точно, когда выполняется для всех . F ( a ) > 0 f ( a ) > 0 a { 0 , 1 } nfF(a)>0f(a)>0a{0,1}n

Я знаю явные полиномы (даже полилинейные), показывающие, что разрыв в размере схемы «вычисляет / считает» может быть экспоненциальным. Мой вопрос касается разрыва "считает / решает".f

Вопрос 1: Кто-нибудь знает какой-нибудь полином который экспоненциально сложнее сосчитать, чем решать по -схемам? { + , × }f{+,×}

В качестве возможного кандидата можно взять многочлен PATH, переменные которого соответствуют ребрам полного графа в , а каждый моном соответствует простому пути от узла к узлу в . Этот полином может быть решено с помощью схемы размера , реализующей, скажем, алгоритм динамического программирования Беллмана-Форда, и это относительно легко показать , что каждый -circuit вычисления пути должен имеют размер . { 1 , , n } 1 n K nKn{1,,n}1nKn{ + , × }O(n3){+,×}2Ω(n)

С другой стороны, каждый контур подсчет PATH решает PATH проблемы, т.е. подсчитывает число -До- путей в указанном с помощью соответствующей - входной подграфа . Это так называемая P -полная проблема . Итак, мы все «верим», что PATH не может иметь счетных -цепей полиномиального размера. «Единственная» проблема - доказать это ... 1 n 0 1 K n ##1n01Kn#{+,×}

Я могу показать, что каждая -схема, подсчитывающая связанный полиномиальный путь Гамильтона, требует экспоненциального размера. Мономы этого многочлена соответствуют -До- путей в , содержащих все узлы. К сожалению, сокращение от HP в PATH по Valiant требует , чтобы вычислить обратную матрицу Вандермонда, и , следовательно , не могут быть реализованы с помощью -circuit.{+,×}п К п1nKn# { + , × }##{+,×}

Вопрос 2: Кто-нибудь видел монотонное сокращение HP до PATH? ###

И наконец:

Вопрос 3: Была ли вообще рассмотрена «монотонная версия» класса P ? #

NB Обратите внимание , что я говорю об очень ограниченном классе схем: монотонная арифметической схеме! В классе -схем, вопрос 1 было бы просто несправедливо задавать вообще: для таких схем нет нижних границ, превышающих , даже когда требуется вычислить данный многочлен на всех входах в , известен. Кроме того, в классе таких цепей, "структурный аналог" Вопроса 1 - существуют ли P -полные полиномы, которые можно определить с помощью -цепей poly-size ? - имеет утвердительный ответ. Таков, например, постоянный полином PER . Ω ( n log n ) R n # { + , - , × } = h S nn i = 1 x i , h ( i ){+,,×}Ω(nlogn)Rn#{+,,×}=hSni=1nxi,h(i)

ДОБАВЛЕНО: Цуёси Ито ответил на вопрос 1 очень простым трюком. Тем не менее, вопросы 2 и 3 остаются открытыми. Статус подсчета PATH интересен сам по себе и потому, что это стандартная проблема DP, и потому что он # P-complete.

Стасис
источник
2
Что касается вопроса 1, как насчет добавления 1 к многочлену, который трудно сосчитать?
Цуёси Ито
2
Ваши три вопроса кажутся достаточно четкими, поэтому они должны быть тремя отдельными вопросами.
Дэвид Ричерби
Я боюсь, что вы не можете избежать тривиальных примеров, просто запретив константы в арифметических схемах. Как насчет добавления x_1 +… + x_n к сложному для подсчета полиному, который принимает 0 в начале координат? (Более того, если вы запрещаете константы, вы не можете представлять полином, который принимает ненулевое значение в начале координат.)
Tsuyoshi Ito
«Как и в« теории #P », под« решением »мы подразумеваем« есть хотя бы одно решение ». И константы не являются решениями (обычно). Знаешь, ты здесь на скользком склоне. Рассмотрим аналог #P Вопроса 1: приведите пример отношений R∈FNP, таких что #R является # P-полным, но легко решить, является ли #R (x)> 0 или нет. У нас может возникнуть соблазн сказать «Совпадение», но это излишество. Добавление тривиального решения в 3SAT прекрасно работает, и мой предыдущий комментарий аналогичен этому. (подробнее)
Цуёси Ито
1
@ Tsuyoshi Ito: Ну, твой простой трюк (сложение суммы всех переменных в сложный для подсчета полином) фактически отвечает на вопрос 1 (в том виде, в котором он был указан). Не могли бы вы выразить это как ответ?
Стасис

Ответы:

7

(Я публикую свои комментарии в качестве ответа в ответ на запрос ОП.)

Что касается вопроса 1, пусть f n : {0,1} n → ℕ - семейство функций, арифметическая схема которых требует экспоненциального размера. Тогда f n +1, но f n +1 легко определить с помощью тривиальной монотонной арифметической схемы. Если вы предпочитаете избегать констант в монотонных арифметических схемах, то пусть f n : {0,1} n → ℕ - семейство функций, такое, что арифметическая схема для f n требует экспоненциального размера и f n (0,…, 0) = 0 и рассмотрим f n + x 1 +… + x n .

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