I will give a short overview of complexity problems of vanishing of various structure constants. I will then discuss our recent result that the vanishing of Schubert coefficients can be decided in probabilistic polynomial time. Joint work with Colleen Robichaux.