The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show the existence by such a method but constructive progress (construction in polynomial time) has been very hard to come by?
An important example is the existence of good codes in coding theory. Using algebraic geometry we can show such objects not only exist but can be constructed in polynomial time.
I am thinking that in addition to graph theoretic and direct combinatorial examples, there should be plenty of natural but very difficult examples from number theory and geometry as well.