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

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

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

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

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

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

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

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

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

И наконец:

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

NB Обратите внимание , что я говорю об очень ограниченном классе схем: монотонная арифметической схеме! В классе -схем, вопрос 1 было бы просто несправедливо задавать вообще: для таких схем нет нижних границ, превышающих , даже когда требуется вычислить данный многочлен на всех входах в , известен. Кроме того, в классе таких цепей, "структурный аналог" Вопроса 1 - существуют ли P -полные полиномы, которые можно определить с помощью -цепей poly-size ? - имеет утвердительный ответ. Таков, например, постоянный полином PER . Ω ( n log n ) R n # { + , - , × } = ∑ h ∈ S n ∏ n i = 1 x i , h ( i $\{+,-,\times\}$$\Omega(n\log n)$$\mathbb{R}^n$$\#$$\{+,-,\times\}$$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$

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

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

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