<p>Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$ variable polynomial $\sum_{(i,j)\in E} \frac{ (x_i - x_j)^2 }{4}$ over the hypercube $\{ -1, 1\}^n$. </p>

<ul>
<li>Is Max-CUT really special or is there always a reduction from a target NP-complete question to Max-CUT so that the optimization version of the target question can also be written as trying to optimize some polynomial over the hypercube? Do we know how to systematically get these special reductions or do they provably not exist or its just that we still don't know? </li>
</ul>

<p>At some level all NP-complete questions are "equivalent" (sure they have variously different approximation hardness properties!) but it seems intuitively a bit unobvious that the optimization versions of each of them can't be written in this form though one of them can trivially be! </p>

<hr>

<p>Is it possible that the different approximation hardness behaviour of the different NP-complete problems is somehow related to this issue of their optimization versions not having an uniform representation as polynomials (one for each) to be optimized over the hypercube? </p>

CC BY-SA 3.0
2016-04-11T21:32:11.020Z
[This paper](http://www.sciencedirect.com/science/article/pii/S1571065304010492) by Tardella explores links between graph-theoretic problems and optimization problems (especially over the hypercube and the simplex). I am not sure if it is what you are looking for, but it does provide interesting insights.
Boson
CC BY-SA 3.0
2016-04-12T14:57:33.423Z
@RickyDemer Could you please expand on your comment? Are you saying that being expressible in unary is iff with being writable as optimization of a polynomial over the hypercube? (And you are saying that this $FP^{\vert \vert FNP }$ is a class of such questions?)
Student
CC BY-SA 3.0
2016-04-12T14:57:46.530Z
@Boson Thanks for the reference! Let me have a look!
Student
CC BY-SA 3.0
2016-04-12T17:22:34.897Z
If your intention is to understand approximability properties, then you need to consider the appropriate class of reductions. For example, if you consider L-reductions, then the class of problems reducible to MaxCut is exactly [MaxSNP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#maxsnp). For some background  on approximation preserving reductions, check [this survey](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=612321)
Sasho Nikolov
CC BY-SA 3.0
2016-04-13T13:53:45.933Z
@SashoNikolov Thanks for the reference! So you mean to say that if a decision question has this Max-CUT like form as that of an unconstrained optimization of a polynomial over the hypercube then this will be preserved under L-reductions? Is that the point?
Student
CC BY-SA 3.0
2016-04-14T01:17:40.053Z
No, I don't think that's exactly what I mean. I wasn't addressing this part of your question directly. I was rather trying to address what looks to me like the motivation for the question: understanding why different NP complete problems have different approximability properties.
Sasho Nikolov
CC BY-SA 3.0
2016-04-14T15:58:20.567Z
Okay! Any thoughts about my curiosity as to whether or not every NP-complete question can be written as an unconstrained polynomial optimization over the hypercube?
Student
CC BY-SA 3.0
2016-04-15T14:30:12.013Z
I wasn't being conscious of this difference. I would think of $\{-1,1\}^n$ as a hypercube. Why isn't it? Does it make a fundamental different to ask the question on this vs say asking the question on the Boolean hypercube $\{0,1\}^n$?
Student
<np-hardness><approximation-algorithms><approximation-hardness><np><np-complete>
About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube
Student
# About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

(Asked by: username_0 on 2016-04-11)

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$ variable polynomial $\sum\_{(i,j)\in E} \frac{ (x\_i - x\_j)^2 }{4}$ over the hypercube $\{ -1, 1\}^n$.

* Is Max-CUT really special or is there always a reduction from a target NP-complete question to Max-CUT so that the optimization version of the target question can also be written as trying to optimize some polynomial over the hypercube? Do we know how to systematically get these special reductions or do they provably not exist or its just that we still don't know?

At some level all NP-complete questions are "equivalent" (sure they have variously different approximation hardness properties!) but it seems intuitively a bit unobvious that the optimization versions of each of them can't be written in this form though one of them can trivially be!

---

Is it possible that the different approximation hardness behaviour of the different NP-complete problems is somehow related to this issue of their optimization versions not having an uniform representation as polynomials (one for each) to be optimized over the hypercube?

**Tags:** np-hardness, approximation-algorithms, approximation-hardness, np, np-complete

> **Comments:**
> **username_1**: [This paper](http://www.sciencedirect.com/science/article/pii/S1571065304010492) by Tardella explores links between graph-theoretic problems and optimization problems (especially over the hypercube and the simplex). I am not sure if it is what you are looking for, but it does provide interesting insights.  
> **username_0**: @RickyDemer Could you please expand on your comment? Are you saying that being expressible in unary is iff with being writable as optimization of a polynomial over the hypercube? (And you are saying that this $FP^{\vert \vert FNP }$ is a class of such questions?)  
> **username_0**: @username_1 Thanks for the reference! Let me have a look!  
> **username_2**: If your intention is to understand approximability properties, then you need to consider the appropriate class of reductions. For example, if you consider L-reductions, then the class of problems reducible to MaxCut is exactly [MaxSNP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#maxsnp). For some background  on approximation preserving reductions, check [this survey](http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=612321)  
> **username_0**: @SashoNikolov Thanks for the reference! So you mean to say that if a decision question has this Max-CUT like form as that of an unconstrained optimization of a polynomial over the hypercube then this will be preserved under L-reductions? Is that the point?  
> **username_2**: No, I don't think that's exactly what I mean. I wasn't addressing this part of your question directly. I was rather trying to address what looks to me like the motivation for the question: understanding why different NP complete problems have different approximability properties.  
> **username_0**: Okay! Any thoughts about my curiosity as to whether or not every NP-complete question can be written as an unconstrained polynomial optimization over the hypercube?  
> **username_0**: I wasn't being conscious of this difference. I would think of $\{-1,1\}^n$ as a hypercube. Why isn't it? Does it make a fundamental different to ask the question on this vs say asking the question on the Boolean hypercube $\{0,1\}^n$?  

---

## 0 answers

