Schwartz–Zippel lemma for polynomial identity testing be derandomized? Does linear programming admit a strongly polynomial-time algorithm? (This is problem #9 in Smale's list of problems.) How many queries are required for envy-free cake-cutting? What is the algorithmic complexity of the minimum spanning tree problem? Equivalently, what is the decision tree complexity of the MST problem? The optimal algorithm to compute MSTs is known, but it relies on decision trees, so its complexity is unknown. Gilbert–Pollack conjecture on the Steiner ratio of the Euclidean plane Programming language theory POPLmark Barendregt–Geuvers–Klop conjecture Other problems Aanderaa–Karp–Rosenberg conjecture Černý Conjecture Generalized star-height problem Separating words problem References External links Open problems around exact algorithms by Gerhard J. Woeginger, Discrete Applied Mathematics 156 (2008) 397–405. The RTA list of open problems – open problems in rewriting. The TLCA List of Open Problems – open problems in area typed lambda calculus. Computer Science Computer Science