  This paper addresses the complexity of SAT-based invariant inference, a
prominent approach to safety verification. We consider the problem of inferring
an inductive invariant of polynomial length given a transition system and a
safety property. We analyze the complexity of this problem in a black-box
model, called the Hoare-query model, which is general enough to capture
algorithms such as IC3/PDR and its variants. An algorithm in this model learns
about the system's reachable states by querying the validity of Hoare triples.
  We show that in general an algorithm in the Hoare-query model requires an
exponential number of queries. Our lower bound is information-theoretic and
applies even to computationally unrestricted algorithms, showing that no choice
of generalization from the partial information obtained in a polynomial number
of Hoare queries can lead to an efficient invariant inference procedure in this
class.
  We then show, for the first time, that by utilizing rich Hoare queries, as
done in PDR, inference can be exponentially more efficient than approaches such
as ICE learning, which only utilize inductiveness checks of candidates. We do
so by constructing a class of transition systems for which a simple version of
PDR with a single frame infers invariants in a polynomial number of queries,
whereas every algorithm using only inductiveness checks and counterexamples
requires an exponential number of queries.
  Our results also shed light on connections and differences with the classical
theory of exact concept learning with queries, and imply that learning from
counterexamples to induction is harder than classical exact learning from
labeled examples. This demonstrates that the convergence rate of
Counterexample-Guided Inductive Synthesis depends on the form of
counterexamples.
