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?

  • $\begingroup$ In my limited experience, the biggest theoretical difference is whether or not the thing being optimized can be expressed in unary. ​ NPO problems for which it can are necessarily in FP$^{||}$$^{\hspace{-0.03 in}\text{F}}$$^{\hspace{-0.03 in}\text{NP}\hspace{-0.03 in}}$$\hspace{-0.4 in}$. ​ ​ ​ ​ $\endgroup$ – user6973 Apr 11 '16 at 19:10
  • $\begingroup$ This paper 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. $\endgroup$ – Boson Apr 11 '16 at 21:32
  • $\begingroup$ @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?) $\endgroup$ – Anirbit Apr 12 '16 at 14:57
  • $\begingroup$ @Boson Thanks for the reference! Let me have a look! $\endgroup$ – Anirbit Apr 12 '16 at 14:57
  • 1
    $\begingroup$ 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. For some background on approximation preserving reductions, check this survey $\endgroup$ – Sasho Nikolov Apr 12 '16 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.