Почему ГАМИЛЬТОНСКИЙ ЦИКЛ так отличается от ПОСТОЯННОГО?

Многочлен является монотонной проекцией многочлена если = poly , и существует присваивание , что . Таким образом, можно заменить каждую переменную из на переменную или константу или так, чтобы полученный многочлен совпадал с . $f(x_1,\ldots,x_n)$m ( n ) π : { y 1 , … , y m } → { x 1 , … , x n , 0 , 1 } f ( x 1 , … , x n ) = g ( π ( y 1 ) , … , $g(y_1,\ldots,y_m)$$m$$(n)$$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$y j g x i 0 1 $f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$$y_j$$g$$x_i$$0$$1$$f$

Меня интересует (причины) различия между постоянным полиномом PER и полиномом гамильтонова цикла HAM: где первое суммирование по всем перестановкам , а второе только по всем циклическим перестановкам .

$$\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \ \mbox{and} \ \ \ \ \mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}$$ $h:[n]\to[n]$$h:[n]\to[n]$

Вопрос: почему HAM не является монотонной проекцией PER? Или это все еще есть?

Я не прошу доказательств , просто по интуитивным причинам.

Мотивация: самая большая известная нижняя граница монотонной цепи для PER (доказанная Разборовым) остается "только" . С другой стороны, результаты Valiant что где с суммированием по всем подмножествам размера . Я сам не мог получить «простое, прямое» сокращение от этих общих результатов, но Алон и Боппана утверждают (в разделе 5), что уже достаточно для этого сокращения. $n^{\Omega(\log n)}$

$$\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}$$ S ⊆ [ n ] | S | = $$\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}$$ $S\subseteq [n]$$|S|=\sqrt{n}$$m=25n^2$

Но подождите: хорошо известно, что для CLIQUE требуются монотонные схемы размером (впервые доказано Алоном и Боппаной с использованием метода Разборова). $2^{n^{\Omega(1)}}$

Итак, если бы HAM была монотонной проекцией PER, мы бы имели нижнюю границу также для PER. $2^{n^{\Omega(1)}}$

На самом деле, почему HAM не является даже немонотонной проекцией PER? Над булева полукольца, бывший NP -полный, в то время как последнее находится в P . Но почему? Где место, где циклическая перестановка делает его таким особенным?

PS Одно очевидное отличие может быть следующим: HAM покрывает [n] только одним (длинным) циклом, тогда как PER может использовать для этого непересекающиеся циклы. Таким образом, для проецирования PER в HAM жесткое направление выглядит следующим образом: убедитесь, что отсутствие гамильтонова цикла подразумевает отсутствие любого покрытия с непересекающимися циклами в новом графе. Это причина того, что HAM не является прогнозом PER?

PPS На самом деле Valiant показал более впечатляющий результат: каждый многочлен с , чей коэффициенты вычислимы по времени p, это проекция (не обязательно монотонная, если ) HAM для = poly . PER также имеет это свойство, но только над полями характеристики . Таким образом, в этом смысле, HAM и PER является действительно «похожи», если мы не будем не в GF (2) где, как помнил Бруно, PER поворачивается к определителю и легко.c u ∈ { 0 , 1 } c u m m ( n ) ≠ $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$$c_u\in\{0,1\}$$c_u$$_m$$m$$(n)$$\neq 2$

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

Пусть и - многочлены с неотрицательными коэффициентами (как в данном случае). Предположим, что является монотонной проекцией под присваиванием (после обозначения вопроса). В каждый моном сопоставляется либо с 0 (если только одна из его переменных сопоставлена ​​с 0), либо с мономом : отмены не может быть из-за неотрицательности.g ( y 1 , … , y m ) f g π π g $f(x_1,\dotsc,x_n)$$g(y_1,\dotsc,y_m)$$f$$g$$\pi$$\pi$$g$$f$

Пусть обозначает многогранник Ньютона функции , и аналогично для .f N e w ( g $New(f)$$f$$New(g)$

Утверждение : существует расширенная формулировка для в , использующая переменные , и число ограничений, не превышающее плюс число ограничений, определяющих .R m ≤ n + m n + m N e w ( g $New(f)$$\mathbb{R}^m$$\leq n+m$$n+m$$New(g)$

Вот как: пусть - координаты (в котором живет ; то есть целая точка в с координатами соответствует ). Для тех , для которых , пересекают с (поскольку в проекцию могут вносить вклад только мономы, не ); это добавляет не более дополнительных ограничений. Пусть обозначает полученный многогранник. Тогда индуцирует линейное отображениер$e_1,\dotsc,e_m$$\mathbb{R}^m$R м ( е 1 , ... , е м ) у й 1 - ⋯ у й м м я π ( у я ) = 0 Н х ш ( г ) { е я = 0 } у я м Р π L π : R m → R n L $New(g)$$\mathbb{R}^m$$(e_1,\dotsc,e_m)$$y_1^{e_1} \dotsb y_m^{e_m}$$i$$\pi(y_i)=0$$New(g)$$\{e_i = 0\}$$y_i$$m$$P$$\pi$$L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$ , так что . Эта последняя часть следует из отсутствия отмен. Таким образом, мы получаем расширенную формулировку для , взяв переменных, ограничения для на переменных и ограничения, определяющие (из которых не более , по одному для каждого ) , Заявка QEDN e w ( f ) n + m P m L π n x $L_{\pi}(P) = New(f)$$New(f)$$n+m$$P$$m$$L_{\pi}$$n$$x_i$

Теперь возьмем в качестве полинома цикла Гамильтона и в качестве перманента и предположим, что является монотонной проекцией . Многогранник Ньютона перманента (и определителя, между прочим), является многогранником покрытия цикла. Этот многогранник легко описывается «реберными» переменными и уравнениями, утверждающими, что каждая вершина имеет степень ровно 2.н г м ф г е и ж$f$$n$$g$$m$$f$$g$$e_{ij}$$m$

Многогранник Ньютона Ветчины. Полином циклов - это многогранник гамильтоновых циклов (удивление, удивление). Но этот многогранник является многогранником TSP, который требует уравнений для описания любой расширенной формулировки$2^{n^{\Omega(1)}}$ , которая, когда субэкспоненциальна, противоречит небольшой расширенной формулировке, данной многогранником покрытия цикла и как указано выше. L $m$$L_{\pi}$

(Обратите внимание, что этот аргумент не выполняется, если , или могут иметь отрицательные коэффициенты, так как тогда могут быть отмены, поэтому не нужно отображать на .)g π L π N e w ( f $f$$g$$\pi$$L_{\pi}$$New(f)$

Интересно отметить, что геометрия этих многогранников тесно связана с тем фактом, что сопоставление находится в то время как цикл Гамильтона является -полным, но я думаю, что приведенные выше рассуждения показывают, как геометрическая структура здесь действительно может добавить что-то за эту классификацию сложности.Н $\mathsf{P}$$\mathsf{NP}$