  We show that time complexity analysis of higher-order functional programs can
be effectively reduced to an arguably simpler (although computationally
equivalent) verification problem, namely checking first-order inequalities for
validity. This is done by giving an efficient inference algorithm for linear
dependent types which, given a PCF term, produces in output both a linear
dependent type and a cost expression for the term, together with a set of proof
obligations. Actually, the output type judgement is derivable iff all proof
obligations are valid. This, coupled with the already known relative
completeness of linear dependent types, ensures that no information is lost,
i.e., that there are no false positives or negatives. Moreover, the procedure
reflects the difficulty of the original problem: simple PCF terms give rise to
sets of proof obligations which are easy to solve. The latter can then be put
in a format suitable for automatic or semi-automatic verification by external
solvers. Ongoing experimental evaluation has produced encouraging results,
which are briefly presented in the paper.
