On the cubic bottleneck in subtyping and flow analysis
Nevin Heintze, David McAllester · 2002
We prove that certain data-flow and control-flow problems are 2NPDA-complete. This means that these problems are in the class 2NPDA and that they are hard for that class. The fact that they are in 2NPDA demonstrates the richness of the class. The fact that they are hard for 2NPDA can be interpreted as evidence they can not be solved in sub-cubic time-the cubic time decision procedure for an arbitrary 2NPDA problem has not been improved since its discovery in 1968.