{
  "id": "1601.07629",
  "version": "v1",
  "published": "2016-01-28T02:44:53.000Z",
  "updated": "2016-01-28T02:44:53.000Z",
  "title": "The Computational Complexity of Duality",
  "authors": [
    "Shmuel Friedland",
    "Lek-Heng Lim"
  ],
  "comment": "13 pages",
  "categories": [
    "math.OC",
    "cs.CC"
  ],
  "abstract": "We show that for any given norm ball or proper cone, weak membership in its dual ball or dual cone is polynomial-time reducible to weak membership in the given ball or cone. A consequence is that the weak membership or membership problem for a ball or cone is NP-hard if and only if the corresponding problem for the dual ball or cone is NP-hard. In a similar vein, we show that computation of the dual norm of a given norm is polynomial-time reducible to computation of the given norm. This extends to convex functions satisfying a polynomial growth condition: for such a given function, computation of its Fenchel dual/conjugate is polynomial-time reducible to computation of the given function. Hence the computation of a norm or a convex function of polynomial-growth is NP-hard if and only if the computation of its dual norm or Fenchel dual is NP-hard. We discuss implications of these results on the weak membership problem for a symmetric convex body and its polar dual, the polynomial approximability of Mahler volume, and the weak membership problem for the epigraph of a convex function with polynomial growth and that of its Fenchel dual.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-28T02:44:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "15B48",
      "52A41",
      "65F35",
      "90C46",
      "90C60"
    ],
    "keywords": [
      "computational complexity",
      "convex function",
      "weak membership problem",
      "dual ball",
      "polynomial growth"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160107629F"
    }
  }
}