The matching polytope has exponential extension complexity - todo314 @ ウィキ

The matching polytope has exponential extension complexity

• Thomas Rothvoss
• STOC 2014

概要

• extension complexityって何？
  • LPで問題を表現した時の不等式の数
• matching polytope
  • マッチングを表現する超多面体
• 結果: matching polytopeをLPで表現するには「指数個の制約」が必要
  • マッチングはPなのに？！
  • ↑ここが驚くべきこと
• 今まで: NP-hardな問題だけだった

Extention Complexity

• TSP polytopeは対称な多項式個の制約式では表現できない
  • LPで簡単には表現できない
  • TSPがLPでかけるからP=NPだよね～を否定

Parity Polytope

• PP_n = 1の個数が奇数の{0,1}^nベクトルの凸包
• x∈PP_nという制約でLPは解ける
• Parity PolytopeはLPで簡単に表現できる？
  • facet（n-1次元の面），つまり不等式制約の数は指数個ある
    • 3次元なら4面体なので4つ
  • 新しい変数を導入して多項式個へ！
  • 観察: パリティごとに考える1,3,5,…
• Parity PolytopeのExtension Complexityは多項式以下: xc(PP_n) = n^O(1)

• Polytope P = {x | Ax ≦ b}
• これは変えて…
  • P = {x | ∃y: Bx+Cy ≦ d}
• こっちのが少ないかも？
• イメージ
  • Qという超多面体をP（より低次元）に射影
  • Qの制約の方が少ないかも

TSP polytope

• TSP polytopeが多項式個の制約で書けると，TSPが多項式個で解けちゃう
• [Yannakakis, 1991]
  • 変数を追加してもだめ～
• [Fiorini et al., 2012]
  • xc(TSP(K_n)) ≧ 2^Ω(√n)

• 最近NP-hardな問題に対して色々と分かってきている
• Pは？

Matching Polytope

• LPで適当に書くと指数個だけど
• 制約をviolateするのはフローとかで多項式時間で判定される
• でも！
• xc(perfect matching polytope) ≧ 2^Ω(n)

STOC

2014-10-03 17:46:30 (Fri)