Higher-Order Interpretations and Program Complexity