There are some algorithms and techniques that will improve static analysis in a greater than linear fashion (however, I wouldn't guarantee exponentially).

see Model Verification: http://en.wikipedia.org/wiki/Kripke_structure_(model_checkin... and SMT solving: http://en.wikipedia.org/wiki/SMT_solver