  Temporal logics for the specification of information-flow properties are able
to express relations between multiple executions of a system. The two most
important such logics are HyperLTL and HyperCTL*, which generalise LTL and CTL*
by trace quantification. It is known that this expressiveness comes at a price,
i.e. satisfiability is undecidable for both logics.
  In this paper we settle the exact complexity of these problems, showing that
both are in fact highly undecidable: we prove that HyperLTL satisfiability is
$\Sigma_1^1$-complete and HyperCTL* satisfiability is $\Sigma_1^2$-complete.
These are significant increases over the previously known lower bounds and the
first upper bounds. To prove $\Sigma_1^2$-membership for HyperCTL*, we prove
that every satisfiable HyperCTL* sentence has a model that is equinumerous to
the continuum, the first upper bound of this kind. We prove this bound to be
tight. Finally, we show that the membership problem for every level of the
HyperLTL quantifier alternation hierarchy is $\Pi_1^1$-complete.
