[Computational Complexity] What is an application?
- What is an application?
- When I took Algebraic Topology the professor said at one point I will now show you an application of homotopy theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use homotopy theory to show that every polynomial with complex coefficients has a complex root The Physics student went back to sleep. (Short sketch of proof: Using Homotopy theory you can show that the complex plane and the punctured complex Plane (remove the origin) are different topologically- the former has trivial homotopy group, while the later has homotopy group Z. Therefore there is no `nice' map between them. If there was a poly p(z) with no roots then you can use this to get a nice map between the two.)
- When I took Ramsey Theory the professor said at one point I will now show you an application of Ramsey theory at which point the one physics major taking the class woke up and said An application! Finally! Is it an application to quantum field theory? The professor said No, we will use Ramsey's Theorem to show that, for all m, there exists an n so that, for all sets of n points in the plane, no three colinear, there exists m that form a convex m-gon. The Physics student went back to sleep. (Short sketch of proof: Let n be the 3-hypergraph ramsey number such that for any 2-coloring of the 3-sets of [n] there is a homogenous set of size m. Given the n points in the plane, color sets-of-three as follows: if the number of points in the triangle formed by the 3 points is ODD then color it RED, otherwise BLUE. There will be m points such that every set of 3 has the same parity inside it. One can show that these m points form a convex hull of an m-gon. First step of this proof: if one of the points is inside the convex hull then its inside a triangle formed by three of the other points. NOTE1: Much better bounds are known. NOTE2: Finding the smallest n is called the Erdos-Szekeres problem or the happy ending problem. See this paper for a survey.)
- I have a website of website of applications of Ramsey Theory to Computer Science. One of the first ones was Yao's paper Should tables be sorted?. This paper shows that in the Cell Probe Model, if the universe is big enough then yes indeed, tables should be sorted. (Short Sketch: Assume there is a scheme for, given n elements of the ordered universe U, stores them in an array of length n cells. Let the universe U be of size the n-hypergraph Ramsey number such that for any n!-coloring of the n-subsets of U there is a homogenous set of size 2n-1. Color an n-subset of U by the permutation it is stored in. There will be 2n-1 elements such that any subset of n is stored in the same permuation. Assume that it is SORTED (if not then it is a fixed perm to make it SORTED). One can show that if the list is sorted then binary search is the best way to find an element. See this paper for a survey. )
So, are these applications or not? The first one applies topology to algebra. The second one applies Ramsey Theory to the Erdos-Szekeres problem. The third applies Ramsey Theory to Data Structures.
The first and third seem like legit applications. The second one is suspect- applying one Erdos-style branch of combinatorics to another. But they are different branches. One metric of how legit an application is might be how far apart the fields are.
Posted By GASARCH to Computational Complexity at 5/12/2008 10:02:00 AM