Abstract
We present a definition of the function pointer aliasing problem for single level function pointers, according to a new approximation of possible program execution for interprocedural analyses in the presence of calls through function pointers. We have classified the complexity of the problem as either polynomial or NP-hard, with respect to various program constructs affecting function pointer aliasing. We present our problem classification and give brief proofs for a polynomial case and a NP-hard case.