Open Problems

Posted on Edited on

大概也不光是 Open Problem，就是一些闲的时候可以思考的问题（

  • 2-player motion planning with 1-toggles EXPTIME-complete? PSAPCE-hard?
  • edge coloring with max degree 3 NP-complete.
  • 2.13 Local optimal solution of monotone, submodular function subject to a matroid is at least half the optimal solution.