Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze

Authors:
  • IHIii H. B. Hunt
    Iii H. B. Hunt
  • DRD. J. Rosenkrantz
    D. J. Rosenkrantz

Abstract
Deterministic exponential lower time bounds are presented for analyzing recursion schemes and recursive programs. The lower bounds for recursion schemes hold for any interpretation with a nontrivial predicate, i.e. a predicate that is neither identically true nor identically false. The lower bounds for recursive programs hold for very simple programs in any recursive programming language with a nontrivial predicate. These lower time bounds hold for the executability, computational identity, totality, divergence, partial correctness, and total correctness problems.

This publication has 11 references indexed in Scilit: