<p>The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone projections of polynomials with nonnegative coefficients lead to the Newton polytope of one being an extended formulation of the Newton polytope of the other, and then applying the recent lower bounds on extended formulations.</p>

<p>Let $f(x_1,\dotsc,x_n)$ and $g(y_1,\dotsc,y_m)$ be polynomials with nonnegative coefficients (as is the case here). Suppose that $f$ is a monotone projection of $g$ under the assignment $\pi$ (following the notation of the question). Under $\pi$, each monomial of $g$ gets mapped either to 0 (iff one of its variables gets mapped to 0) or to a monomial of $f$: there can't be any cancellations because of non-negativity. </p>

<p>Let $New(f)$ denote the Newton polytope of $f$, and similarly for $New(g)$.</p>

<p><em>Claim</em>: there is an extended formulation for $New(f)$ in $\mathbb{R}^m$, using $\leq n+m$ variables, and a number of constraints that is at most $n+m$ plus the number of constraints defining $New(g)$.</p>

<p>Here's how: Let $e_1,\dotsc,e_m$ be the coordinates on $\mathbb{R}^m$ (in which $New(g)$ lives; viz., an integer point in $\mathbb{R}^m$ with coordinates $(e_1,\dotsc,e_m)$ corresponds to the monomial $y_1^{e_1} \dotsb y_m^{e_m}$). For those $i$ such that $\pi(y_i)=0$, intersect $New(g)$ with $\{e_i = 0\}$ (since only monomials that do not involve $y_i$ can contribute to the projection); this adds at most $m$ additional constraints. Let $P$ denote the resulting polytope. Then $\pi$ induces a linear map $L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$, such that $L_{\pi}(P) = New(f)$. This last part follows from the lack of cancellations. Thus we get an extended formulation for $New(f)$ by taking $n+m$ variables, the constraints for $P$ on the $m$ variables, and the constraints defining $L_{\pi}$ (of which there are at most $n$, one for each $x_i$). QED Claim</p>

<p>Now take $f$ to be the $n$-th Hamilton cycle polynomial and $g$ to be the $m$-th permanent, and suppose that $f$ is a monotone projection of $g$. The Newton polytope of the permanent (and determinant, incidentally), is the cycle cover polytope. This polytope is easily described by the "edge" variables $e_{ij}$ and the $m$ equations stating that every vertex has degree exactly 2.</p>

<p>The Newton polytope of the Ham. Cycle polynomial is the Hamiltonian cycle polytope (surprise, surprise). But this polytope is the TSP polytope, which <a href="http://arxiv.org/abs/1111.0837">requires $2^{n^{\Omega(1)}}$ equations to describe <em>any extended formulation of</em></a>, which, when $m$ is subexponential, contradicts the small extended formulation given by the cycle cover polytope and $L_{\pi}$ as above.</p>

<p>(Note that this argument fails if $f$, $g$, or $\pi$ can have negative coefficients, as then there can be cancellations, so $L_{\pi}$ need not map onto $New(f)$.)</p>

<p>It's interesting to note that the geometry of these polytopes is closely related to the fact that matching is in $\mathsf{P}$ while Hamilton cycle is $\mathsf{NP}$-complete, but I think the above reasoning shows how the geometric structure here really can add something beyond that complexity classification.</p>

CC BY-SA 3.0
2015-08-17T08:31:45.260Z
a very nice argument. This is exactly what I looked for! Indeed, extended LP formulations simulate Valiant's projections (at least monotone).
Stasys
CC BY-SA 3.0
2015-08-16T01:38:37.410Z
2015-08-22T02:00:14.943Z
2015-08-22T02:00:14.943Z
Joshua Grochow
<p>A polynomial <span class="math-container">$f(x_1,\ldots,x_n)$</span> is a <i>monotone projection</i> of a
polynomial <span class="math-container">$g(y_1,\ldots,y_m)$</span> if <span class="math-container">$m$</span> = poly<span class="math-container">$(n)$</span>, and there is an assignment
<span class="math-container">$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$</span>  such that <span class="math-container">$f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$</span>. That is, it is possible to
replace each variable <span class="math-container">$y_j$</span> of <span class="math-container">$g$</span> by a variable <span class="math-container">$x_i$</span> or a constant <span class="math-container">$0$</span> or <span class="math-container">$1$</span> so that
the resulting polynomial coincides with <span class="math-container">$f$</span>.</p>
<p>
I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial HAM:
<span class="math-container">$$
\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)}
$$</span>
where the first summation is over  <i>all</i> permutations <span class="math-container">$h:[n]\to[n]$</span>,
and the second is only over all <i>cyclic</i> permutations <span class="math-container">$h:[n]\to[n]$</span>.
 <blockquote>
<b>Question:</b> Why HAM is <b>not</b> a monotone projection PER? Or it still is?
</blockquote>
I am not asking for <i>proofs</i>, just for intuitive reasons.
<p>
Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" <span class="math-container">$n^{\Omega(\log n)}$</span>. On the other hand, results of
[Valiant](https://web.vu.lt/mif/s.jukna/boolean/valiant-completeness.pdf) imply that
<span class="math-container">$$
\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}
$$</span>
where
<span class="math-container">$$
\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i &lt; j\in S}x_{i,j}
$$</span>
with the summation is over all subsets <span class="math-container">$S\subseteq [n]$</span> of size <span class="math-container">$|S|=\sqrt{n}$</span>. I myself couldn't get a "simple, direct" reduction form these general results, but [Alon and Boppana](https://web.vu.lt/mif/s.jukna/boolean/Alon-Boppana.pdf) claim (in Sect. 5) that already <span class="math-container">$m=25n^2$</span> is sufficient for this reduction.
<p>
But wait: it is well known that CLIQUE requires monotone circuits of size <span class="math-container">$2^{n^{\Omega(1)}}$</span> (first proved by Alon and Boppana using Razborov's method).
<p>
So, were HAM a monotone projection of PER, we would have <span class="math-container">$2^{n^{\Omega(1)}}$</span> lower bound also for PER.
<p>
Actually, <i>why</i> HAM is not even a <b>non-monotone</b> projection  of PER? Over the boolean semiring, the former is <b>NP</b>-complete, while the latter is in <b>P</b>. But why? Where is a place where being <b>cyclic</b> for a permutation makes it so special?
<p>
<b>P.S.</b> One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the <i>absence</i> of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER? 
<p>
<b>P.P.S.</b> Actually, Valiant proved a more impressing result: every polynomial <span class="math-container">$f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$</span> with <span class="math-container">$c_u\in\{0,1\}$</span>, whose coefficients <span class="math-container">$c_u$</span> are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM<span class="math-container">$_m$</span> for <span class="math-container">$m$</span> = poly<span class="math-container">$(n)$</span>. PER also has this property, but only over fields of characteristic <span class="math-container">$\neq 2$</span>. So, in this sense, HAM and PER <i>are</i> indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy.

CC BY-SA 3.0
2014-11-20T03:57:37.350Z
I have a question a bit off the topic. May I ask why PERMANENT is in P over the boolean semiring? I'm not aware of such an algorithm.
caozhu
CC BY-SA 3.0
2014-11-20T07:23:11.757Z
@caozhu: This is simply since PERMANENT is the same as DETERMINANT over the boolean semiring. The algorithm is then any DETERMINANT algorithm.
Bruno
CC BY-SA 3.0
2014-11-20T10:23:36.910Z
@Bruno: not quite. You are right if we are in the field GF(2); then we can use, say, Gauss. Still,  boolean $\{\lor,\land,\neg\}$ circuit for PER of size about $n^{5/2}$ can be constructed using [Hopcroft-Karp algorithm](http://epubs.siam.org/doi/abs/10.1137/0202019) for maximum matching, or just Floyd-Fulkerson maximum flaw algorithm.
Stasys
<cc.complexity-theory><circuit-complexity><lower-bounds><arithmetic-circuits>
Why is HAMILTONIAN CYCLE so different from PERMANENT?
Stasys
# Why is HAMILTONIAN CYCLE so different from PERMANENT?

(Asked by: username_0 on 2014-11-18)

A polynomial $f(x\_1,\ldots,x\_n)$ is a *monotone projection* of a
polynomial $g(y\_1,\ldots,y\_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y\_1,\ldots,y\_m\}\to\{x\_1,\ldots,x\_n, 0,1\}$ such that $f(x\_1,\ldots,x\_n)=g(\pi(y\_1),\ldots,\pi(y\_m))$. That is, it is possible to
replace each variable $y\_j$ of $g$ by a variable $x\_i$ or a constant $0$ or $1$ so that
the resulting polynomial coincides with $f$.

I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial 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)}
$$
where the first summation is over *all* permutations $h:[n]\to[n]$,
and the second is only over all *cyclic* permutations $h:[n]\to[n]$.
> **Question:** Why HAM is **not** a monotone projection PER? Or it still is?

I am not asking for *proofs*, just for intuitive reasons.

Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" $n^{\Omega(\log n)}$. On the other hand, results of
[Valiant](https://web.vu.lt/mif/s.jukna/boolean/valiant-completeness.pdf) imply that
$$
\mbox{CLIQUE$\_n$ is a monotone projection of HAM$\_{m}$}
$$
where
$$
\mbox{CLIQUE}\_n(x)=\sum\_{S}\prod\_{i < j\in S}x\_{i,j}
$$
with the summation is over all subsets $S\subseteq [n]$ of size $|S|=\sqrt{n}$. I myself couldn't get a "simple, direct" reduction form these general results, but [Alon and Boppana](https://web.vu.lt/mif/s.jukna/boolean/Alon-Boppana.pdf) claim (in Sect. 5) that already $m=25n^2$ is sufficient for this reduction.

But wait: it is well known that CLIQUE requires monotone circuits of size $2^{n^{\Omega(1)}}$ (first proved by Alon and Boppana using Razborov's method).

So, were HAM a monotone projection of PER, we would have $2^{n^{\Omega(1)}}$ lower bound also for PER.

Actually, *why* HAM is not even a **non-monotone** projection of PER? Over the boolean semiring, the former is **NP**-complete, while the latter is in **P**. But why? Where is a place where being **cyclic** for a permutation makes it so special?

**P.S.** One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the *absence* of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER?

**P.P.S.** Actually, Valiant proved a more impressing result: every polynomial $f(x)=\sum\_{u\subseteq [n]}c\_u\prod\_{i\in u}x\_i$ with $c\_u\in\{0,1\}$, whose coefficients $c\_u$ are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM$\_m$ for $m$ = poly$(n)$. PER also has this property, but only over fields of characteristic $\neq 2$. So, in this sense, HAM and PER *are* indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy.

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, arithmetic-circuits
> **Comments:**
> **username_1**: I have a question a bit off the topic. May I ask why PERMANENT is in P over the boolean semiring? I'm not aware of such an algorithm.  
> **username_2**: @caozhu: This is simply since PERMANENT is the same as DETERMINANT over the boolean semiring. The algorithm is then any DETERMINANT algorithm.  
> **username_0**: @Bruno: not quite. You are right if we are in the field GF(2); then we can use, say, Gauss. Still,  boolean $\{\lor,\land,\neg\}$ circuit for PER of size about $n^{5/2}$ can be constructed using [Hopcroft-Karp algorithm](http://epubs.siam.org/doi/abs/10.1137/0202019) for maximum matching, or just Floyd-Fulkerson maximum flaw algorithm.  

---

## 1 answers

### Answer by username_3 on 2015-08-16. Score: 14 | Accepted answer

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone projections of polynomials with nonnegative coefficients lead to the Newton polytope of one being an extended formulation of the Newton polytope of the other, and then applying the recent lower bounds on extended formulations.

Let $f(x\_1,\dotsc,x\_n)$ and $g(y\_1,\dotsc,y\_m)$ be polynomials with nonnegative coefficients (as is the case here). Suppose that $f$ is a monotone projection of $g$ under the assignment $\pi$ (following the notation of the question). Under $\pi$, each monomial of $g$ gets mapped either to 0 (iff one of its variables gets mapped to 0) or to a monomial of $f$: there can't be any cancellations because of non-negativity.

Let $New(f)$ denote the Newton polytope of $f$, and similarly for $New(g)$.

*Claim*: there is an extended formulation for $New(f)$ in $\mathbb{R}^m$, using $\leq n+m$ variables, and a number of constraints that is at most $n+m$ plus the number of constraints defining $New(g)$.

Here's how: Let $e\_1,\dotsc,e\_m$ be the coordinates on $\mathbb{R}^m$ (in which $New(g)$ lives; viz., an integer point in $\mathbb{R}^m$ with coordinates $(e\_1,\dotsc,e\_m)$ corresponds to the monomial $y\_1^{e\_1} \dotsb y\_m^{e\_m}$). For those $i$ such that $\pi(y\_i)=0$, intersect $New(g)$ with $\{e\_i = 0\}$ (since only monomials that do not involve $y\_i$ can contribute to the projection); this adds at most $m$ additional constraints. Let $P$ denote the resulting polytope. Then $\pi$ induces a linear map $L\_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$, such that $L\_{\pi}(P) = New(f)$. This last part follows from the lack of cancellations. Thus we get an extended formulation for $New(f)$ by taking $n+m$ variables, the constraints for $P$ on the $m$ variables, and the constraints defining $L\_{\pi}$ (of which there are at most $n$, one for each $x\_i$). QED Claim

Now take $f$ to be the $n$-th Hamilton cycle polynomial and $g$ to be the $m$-th permanent, and suppose that $f$ is a monotone projection of $g$. The Newton polytope of the permanent (and determinant, incidentally), is the cycle cover polytope. This polytope is easily described by the "edge" variables $e\_{ij}$ and the $m$ equations stating that every vertex has degree exactly 2.

The Newton polytope of the Ham. Cycle polynomial is the Hamiltonian cycle polytope (surprise, surprise). But this polytope is the TSP polytope, which [requires $2^{n^{\Omega(1)}}$ equations to describe *any extended formulation of*](http://arxiv.org/abs/1111.0837), which, when $m$ is subexponential, contradicts the small extended formulation given by the cycle cover polytope and $L\_{\pi}$ as above.

(Note that this argument fails if $f$, $g$, or $\pi$ can have negative coefficients, as then there can be cancellations, so $L\_{\pi}$ need not map onto $New(f)$.)

It's interesting to note that the geometry of these polytopes is closely related to the fact that matching is in $\mathsf{P}$ while Hamilton cycle is $\mathsf{NP}$-complete, but I think the above reasoning shows how the geometric structure here really can add something beyond that complexity classification.

> **Comments:**
> **username_0**: a very nice argument. This is exactly what I looked for! Indeed, extended LP formulations simulate Valiant's projections (at least monotone).  

---

