On Average-Case Hardness of Higher-Order Model Checking

Yoshiki Nakamura, Kazuyuki Asada, Naoki Kobayashi, Ryoma Sin'ya, Takeshi TsukadaFSCD 2020 · OpenReview

TL;DR

This paper investigates the average-case complexity of higher-order model checking, a crucial problem in verifying complex functional programs. Despite efficient tools existing for typical inputs, the authors demonstrate that, for almost all "minimal" terms (those without useless sub-expressions), the problem remains computationally hard, specifically k-EXPTIME hard on average with respect to the automaton size. This suggests that the efficiency of current tools might rely on specific properties of the programs they encounter, rather than a general ease of the problem.

What Problem Does This Paper Address?

Higher-order model checking (HOMC) is the problem of determining if a tree generated by a higher-order term (like those in the λY-calculus or higher-order recursion schemes) is accepted by a given tree automaton. This problem is fundamental for verifying complex functional programs, which often generate potentially infinite trees. While the worst-case complexity of HOMC is known to be very high (k-EXPTIME complete for order-k terms), practical tools exist that perform well on typical inputs. This discrepancy raises a key question: is HOMC actually easier on average, meaning hard instances are rare? This paper tackles this question by investigating the average-case hardness of HOMC, aiming to understand why practical tools are efficient despite the daunting worst-case complexity.

Methods

The authors introduce a novel intersection type system designed to precisely characterize "minimal" terms. A minimal term is one that doesn't contain any "useless" subterms – subterms whose removal wouldn't change the generated tree. This characterization is crucial because terms with useless subterms can trivially be solved efficiently, masking the true complexity of the problem.

The core of their argument relies on a "mixture" of average-case and worst-case analysis. They first establish that for almost every minimal term of a certain order, the HOMC problem specialized to that term is k-EXPTIME hard. This is achieved by:

  1. Decomposition: Leveraging existing work on quantitative analysis of λ-terms, they decompose terms into contexts and subterms.
  2. "Infinite Monkey Theorem" Analogy: They adapt the idea that almost any random word contains a given subword to terms. Specifically, they show that almost every minimal term contains a known "hard" term (tHARD,k) as a subterm.
  3. Type System for Minimality: The novel intersection type system is used to prove that if a term is minimal, and it contains a hard term, then the HOMC problem for that term is also hard. This system ensures that the "hard" subterm is actually "used" in the computation of the term's value tree.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Average-Case Hardness is Still Hard: The most striking insight is that even when considering "typical" or "minimal" terms, higher-order model checking remains computationally challenging on average. This suggests that the efficiency of current tools might be due to specific properties of the programs they are applied to, rather than the inherent ease of the problem itself.
  • The Importance of "Useless" Subterms: The paper highlights that terms with "useless" subterms can be solved trivially. By focusing on "minimal" terms (those without such subterms), the authors reveal the true average-case complexity, which is still high. This distinction is crucial for understanding the problem's landscape.
  • Intersection Types as a Tool for Minimality: The development of a novel intersection type system that precisely characterizes minimal terms is a significant technical contribution. This system is key to proving that a term is minimal and that its subterms are "used" in a way that preserves complexity.
  • A "Mixture" of Analyses: The paper employs a sophisticated proof strategy that combines average-case analysis (on the choice of terms) with worst-case analysis (on the choice of automata). This allows them to make strong claims about the hardness of the problem for typical inputs.

Key Results

The main result is Theorem 7: For sufficiently large parameters, the ratio of k-EXPTIME hard terms to the total number of minimal terms of order-k and size n tends to 1 as n approaches infinity. In simpler terms, if you pick a "minimal" higher-order term of a given order and size at random, it is highly likely that the higher-order model checking problem for that term will be k-EXPTIME hard. This applies to terms with internal arity up to 1 and a limited number of variables.

Limitations and Future Work

  • "Minimal" Terms: The result applies to "minimal" terms, which are defined as those without useless subterms. While this restriction is argued to be natural for program verification applications, it's a specific subset of all possible terms. The authors acknowledge that terms with useless subterms can be solved efficiently.
  • "Mixture" of Analyses: The result is a "mixture" of average-case and worst-case analysis. The authors state that a pure average-case analysis (in the sense of distributional complexity) is left for future work.
  • Future Work: The paper explicitly mentions that a pure average-case analysis of the hardness of higher-order model checking is left for future work. They also suggest that their type-based characterization of minimal terms might be of independent interest.

Summary updated

Abstract

We study a mixture between the average case and worst case complexities of higher-order model checking, the problem of deciding whether the tree generated by a given λ Y-term (or equivalently, a higher-order recursion scheme) satisfies the property expressed by a given tree automaton. Higher-order model checking has recently been studied extensively in the context of higher-order program verification. Although the worst-case complexity of the problem is k-EXPTIME complete for order-k terms, various higher-order model checkers have been developed that run efficiently for typical inputs, and program verification tools have been constructed on top of them. One may, therefore, hope that higher-order model checking can be solved efficiently in the average case, despite the worst-case complexity. We provide a negative result, by showing that, under certain assumptions, for almost every term, the higher-order model checking problem specialized for the term is k-EXPTIME hard with respect to the size of automata. The proof is based on a novel intersection type system that characterizes terms that do not contain any useless subterms.
BibTeX
@inproceedings{nakamura2020average,
  author = {Yoshiki Nakamura and Kazuyuki Asada and Naoki Kobayashi and Ryoma Sin'ya and Takeshi Tsukada},
  title = {{On Average-Case Hardness of Higher-Order Model Checking}},
  booktitle = {FSCD},
  year = {2020},
  url = {https://openreview.net/forum?id=iQxIYdEF9H},
}
Figure