\section{Proofs for Section~\ref{sec:hardness}}\label{app:hardness}

\subsection{The gadgets}

\lembayesgadget*

\begin{proof}[Proof of \cref{lem:bayesgadget}]
\begin{steps}
\step{1}{1} $\Gamma_F$ is a $(k+1)$-CNF with $M+n+1$ clauses, none of them tautological.
\pf A clause $\neg a\vee C$ has width $|C|+1\le k+1$ and is tautological only if $C$ is, because $a$ does not
occur in $C$. The clauses $a\vee\neg z_i$ and $a\vee\neg u$ have width $2\le k+1$ and are not tautological. The
$M+n+1$ clauses are distinct.
\step{1}{2} The satisfying assignments with $a=1$ are the assignments $(z,1,u)$ with $z$ satisfying $F$ and
$u\in\{0,1\}$; there are $2\#F$ of them.
\pf With $a=1$ the clauses $a\vee\neg z_i$ and $a\vee\neg u$ hold and $\neg a\vee C$ is equivalent to $C$.
\step{1}{3} Exactly one satisfying assignment has $a=0$, namely $z=0^n$, $u=0$.
\pf With $a=0$ the clauses $\neg a\vee C$ hold, $a\vee\neg z_i$ forces $z_i=0$, and $a\vee\neg u$ forces $u=0$.
\qedstep{1}{4}
\end{steps}
\end{proof}

\lembayescontexts*

\begin{proof}[Proof of \cref{lem:bayescontexts}]
\begin{steps}
\step{1}{1} Part~(a) holds, with a bijection between $\VS(S^{\LD}_F)$ and the satisfying assignments of
$\Gamma_F$ that preserves the value of $a$.
\pf Index the $n+2$ coordinates by $z_1,\dots,z_n,a,u$. For each clause $D$ of $\Gamma_F$, let $x_D$ have entry
$+1$ at the variables that occur positively in $D$, $-1$ at those that occur negatively, and $0$ elsewhere;
it is well defined because $D$ is not tautological, and $|\supp(x_D)|=|D|\le k+1$. By \cref{ex:local}(a),
$h_\sigma(x_D)=1$ if and only if the assignment with value $(1+\sigma_i)/2$ at coordinate $i$ satisfies $D$.
So $\sigma\mapsto((1+\sigma_i)/2)_i$ maps $\VS(S^{\LD}_F)$ bijectively onto the satisfying assignments of
$\Gamma_F$, and the coordinate of $a$ is $+1$ exactly when $a=1$.
\step{1}{2} Part~(b) holds, with a bijection between $\VS(S^{\BP}_F)$ and the satisfying assignments of
$\Gamma_F$ that preserves the value of $a$.
\pf $\Gamma_F$ is a $(k+1)$-CNF without tautological clauses on $n+2$ variables (\cref{lem:bayesgadget}).
\Cref{fact:gadget} with $k+1\ge3$ in place of $k$ gives $p=k-1$ padding coordinates, $M+n+1+(k-1)=M+n+k$
examples in dimension $n+2+k-1=n+k+1$, all labeled $1$, with supports of size at most $2(k+1)-2=2k$. A sign
vector is consistent if and only if its padding coordinates are $1$ and the assignment $\ind[\sigma_i=1]$ of the
first $n+2$ coordinates satisfies $\Gamma_F$; this is a bijection, and it reads $a$ off the coordinate of $a$.
\step{1}{3} In both contexts, $h(e_a)=1$ exactly for the descriptions whose assignment has $a=1$.
\pf For literal disjunctions, $\supp(e_a)=\{a\}$, so $h_\sigma(e_a)=1$ if and only if $\sigma_a=1$. For binarized
perceptrons, $\langle\sigma,e_a\rangle=\sigma_a\ge0$ if and only if $\sigma_a=1$.
\step{1}{4} $p_S(e_a)=2\#F/(2\#F+1)$ in both contexts, and both are consistent.
\pf Without noise the posterior is uniform on the version space, which by \sref{1}{1} and \sref{1}{2} is in
bijection with the $2\#F+1\ge1$ satisfying assignments of $\Gamma_F$, of which $2\#F$ have $a=1$
(\cref{lem:bayesgadget}). Apply \sref{1}{3}.
\qedstep{1}{5}
\pf If $\#F=0$ the predictive is $0$, and if $\#F\ge1$ it is $2\#F/(2\#F+1)\ge2/3$. Solving
$p=2\#F/(2\#F+1)$ gives $\#F=p/(2(1-p))$. The constructions take polynomial time.
\end{steps}
\end{proof}

\lemlengthgadget*

\begin{proof}[Proof of \cref{lem:lengthgadget}]
\begin{steps}
\step{1}{1} One can compute in polynomial time a $3$-CNF $F'$ without tautological clauses, with $n\le2L$
variables and $M\le L$ clauses, that is satisfiable if and only if $F$ is.
\pf Delete the tautological clauses of $F$ and the variables that no longer occur; this changes neither
satisfiability nor the bounds. Replace each clause $\ell_1\vee\dots\vee\ell_r$ with $r\ge4$ by the $r-2$ clauses
$\ell_1\vee\ell_2\vee t_1$, $\neg t_1\vee\ell_3\vee t_2$, \dots, $\neg t_{r-3}\vee\ell_{r-1}\vee\ell_r$ with $r-3$
fresh variables. An assignment that satisfies the clause extends to one that satisfies the chain: set
$t_j=1$ for the indices $j$ before the clause of the chain that contains the first true literal, and $t_j=0$
after it. If every $\ell_i$ is false, the chain forces $t_1=1$, then $t_2=1$, and so on, and its last clause
fails. The occurring variables number at most $L$, the fresh ones at most $\sum_C\max\{0,|C|-3\}\le L$, and the
clauses at most $\sum_C\max\{1,|C|-2\}\le L$. No new clause is tautological.
\step{1}{2} \Let $\Gamma'$ be the CNF on the variables $z$ of $F'$, one fresh variable $y_C$ for each clause $C$
of $F'$ of width $3$, and two more variables $a,u$, with the clauses: $\neg a\vee C$ for each clause $C$ of $F'$
of width at most $2$; $\neg a\vee\ell_1\vee y_C$, $\neg y_C\vee\ell_2\vee\ell_3$ and $a\vee\neg y_C$ for each
clause $C=\ell_1\vee\ell_2\vee\ell_3$; $a\vee\neg z$ for each variable $z$ of $F'$; and $a\vee\neg u$. Then
$\Gamma'$ is a $3$-CNF without tautological clauses on $N\le n+M+2\le3L+2$ variables with at most
$\min\{5L+1,36N^2\}$ clauses.
\pf The fresh variables are distinct, and $F'$ has no tautological clause. Let $F_0$ be $F$ without its
tautological clauses, $L_0\le L$ its length, and $n_0\le N$ the number of its variables. The bounds of
\sref{1}{1} hold with $L_0$ in place of $L$, so $\Gamma'$ has at most $3M+n+1\le5L_0+1$ clauses. The clauses of $F_0$
of width at most $2$ are distinct and not tautological, so there are at most $2n_0+4\binom{n_0}2\le2N^2$ of them,
of total length at most $4N^2$. A clause of $F_0$ of width $r\ge3$ gives $\Gamma'$ at least $r/3$ variables of its
own: one variable $y_C$ if $r=3$, and $r-3$ chain variables and $r-2$ variables $y_C$ if $r\ge4$. So these clauses
have total length at most $3N$. Hence $L_0\le4N^2+3N\le7N^2$ and $5L_0+1\le36N^2$.
\step{1}{3} Exactly one satisfying assignment of $\Gamma'$ has $a=0$.
\pf With $a=0$ the clauses $a\vee\neg z$, $a\vee\neg y_C$ and $a\vee\neg u$ force all other variables to $0$.
The all-zero assignment of them satisfies $\neg a\vee\dots$ through $\neg a$ and $\neg y_C\vee\ell_2\vee\ell_3$
through $\neg y_C$.
\step{1}{4} The number $A$ of satisfying assignments of $\Gamma'$ with $a=1$ is $0$ if $F'$ is unsatisfiable and at
least $2$ otherwise.
\pf With $a=1$, the clauses with the literal $a$ hold, $\neg a\vee C$ reduces to $C$, and the two clauses of a
clause $C$ of width $3$ reduce to $(\ell_1\vee y_C)\wedge(\neg y_C\vee\ell_2\vee\ell_3)$. For a fixed $z$, this
has a solution $y_C$ if and only if $z$ satisfies $C$: if $\ell_1$ is true, $y_C=0$ works; if $\ell_1$ is false,
$y_C$ must be $1$, which works if and only if $\ell_2\vee\ell_3$ holds. So the assignments with $a=1$ exist only
for $z$ satisfying $F'$, each such $z$ has at least one choice of every $y_C$, and $u$ is free.
\step{1}{5} The positive examples of $\LD_3$ for the clauses of $\Gamma'$ form a consistent context in dimension
$N$ with at most $\min\{5L+1,36N^2\}$ examples, and the query $e_a$ has posterior predictive $A/(A+1)$, which is
$0$ if $F$ is unsatisfiable and at least $2/3$ otherwise.
\pf As in \sref{1}{1} and \sref{1}{3}--\sref{1}{4} of the proof of \cref{lem:bayescontexts}, the version space
is in bijection with the satisfying assignments of $\Gamma'$, and $e_a$ is labeled by $a$. Apply \sref{1}{3},
\sref{1}{4} and \sref{1}{1}.
\qedstep{1}{6}
\pf For $\BP_4$, apply \cref{fact:gadget} to $\Gamma'$ with $k=3$: one padding coordinate and one more example,
supports of size at most $4$, and the same bijection, as in \sref{1}{2} of the proof of
\cref{lem:bayescontexts}. All steps take polynomial time.
\end{steps}
\end{proof}

\subsection{Lower bounds}

\thmhardness*

\begin{proof}[Proof of \cref{thm:hardness}]
\begin{steps}
\step{1}{1} If an algorithm $\mathcal A$ outputs a number within $1/4$ of $p_S(e_a)$, with error probability at
most $1/3$, on a context $S$ of \cref{lem:bayescontexts} or \cref{lem:lengthgadget}, then one run of $\mathcal A$
decides the satisfiability of $F$ with error probability at most $1/3$. The same holds for an algorithm that
computes $\Bayes(S,e_a)$, and for $O(1)$ runs of the Gibbs predictor, exact or within statistical distance
$1/6$.
\pf The predictive is $0$ if $F$ is unsatisfiable and at least $2/3$ otherwise, so a number within $1/4$ of it is
at most $1/4$ in the first case and at least $5/12$ in the second; answer ``satisfiable'' when it exceeds $1/3$.
$\Bayes(S,e_a)=1$ exactly when the predictive is at least $1/2$, that is, when $F$ is satisfiable. A run of the
Gibbs predictor outputs $1$ with probability at most $1/6$ in the first case and at least $1/2$ in the second;
twelve runs and the answer ``satisfiable'' when at least four of them output $1$ err with probability less
than $1/7$ in the first case and at most $299/4096<1/13$ in the second.

\step{1}{2} Part~\ref{it:seth} holds under \cref{hyp:cnfseth}.
\begin{steps}
\step{2}{1} \Let $K',c'$ be given by \cref{fact:logsat} for $\gamma/2$, and \Let $K=2K'$ and $c_\gamma=c'+1$.
\Assume an algorithm $\mathcal A$ that does what part~\ref{it:seth} excludes, in time $O(2^{(1-\gamma)N})$.
\step{2}{2} Given a $k$-CNF $F$ on $n$ variables with $k\le K'\log n$ and at most $n^{c'}$ clauses, with $n$ large,
\Let $k_0=\max\{2,\lfloor K'\log n\rfloor\}$, delete the tautological clauses of $F$, and build $S^{\BP}_F$ by
\cref{lem:bayescontexts} with $k_0$ in place of $k$. Then $S^{\BP}_F$ is a consistent context of at most
$N^{c_\gamma}$ positive examples of $\BP_{\lceil K\log N\rceil}$ in dimension $N=n+k_0+1$.
\pf $F$ is a $k_0$-CNF. The supports have size at most $2k_0\le2K'\log n\le K\log N$, and the context has at most
$n^{c'}+n+k_0\le N^{c'+1}$ examples for large $n$.
\step{2}{3} Running $\mathcal A$ on $(S^{\BP}_F,e_a)$ decides $F$ in time $O(2^{(1-\gamma/2)n})$ with error
probability at most $1/3$.
\pf By \sref{1}{1}. The time is $\poly(n)+O(2^{(1-\gamma)(n+K'\log n+1)})=O(2^{(1-\gamma)n}n^{K'})$, which is
$O(2^{(1-\gamma/2)n})$.
\step{2}{4} The same argument applies to $\LD_{\lceil K\log N\rceil}$ with $S^{\LD}_F$, of dimension $n+2$ and
supports of size at most $k_0+1\le K\log N$, and to $\Bayes$ and the Gibbs predictor by \sref{1}{1}.
\qedstep{2}{5}
\pf \sref{2}{3} contradicts \cref{fact:logsat}.
\end{steps}

\step{1}{3} Part~\ref{it:seth} holds under \cref{hyp:cnfeth}.
\pf \Cref{fact:logsat} gives $K',c',\rho'$ for time $O(2^{\rho'n})$. With $K=2K'$, $c_\gamma=c'+1$ and $\rho=\rho'/2$,
the construction of \sref{1}{2} turns an algorithm in time $O(2^{\rho N})$ into one in time
$O(2^{\rho n}n^{K'})=O(2^{\rho'n})$.

\step{1}{4} Part~\ref{it:len} holds.
\begin{steps}
\step{2}{1} \Assume an algorithm $\mathcal A$ that, for all sufficiently large $N$, does what
part~\ref{it:len} excludes in time $2^{f(N)}$, where $f(N)=N/(\log N)^{C+\theta}$.
\step{2}{2} Given a CNF $F$ of length $L$, build the context of \cref{lem:lengthgadget}, of dimension
$N_F\le3L+2$, and run $\mathcal A$. This decides the satisfiability of $F$ with error probability at most $1/3$.
\pf By \sref{1}{1}.
\step{2}{3} The time is at most $2^{L/(\log L)^C}$ for all sufficiently large $L$.
\pf The context has dimension $N_F\le3L+2$ and at most $36N_F^2$ examples, so it is an input of the kind that
$\mathcal A$ handles. Below any fixed dimension there are only finitely many such contexts, because their size is
bounded, so on them $\mathcal A$ takes time $O(1)$. The function $f$ is nondecreasing for $N\ge e^{C+\theta}$. For
large $L$, $f(3L+2)\le4L/(\log L)^{C+\theta}\le L/(2(\log L)^C)$ once $(\log L)^\theta\ge8$, so the time is
$\poly(L)+O(1)+2^{L/(2(\log L)^C)}\le2^{L/(\log L)^C}$.
\step{2}{4} The same holds for $\BP_4$ in dimension $N_F+1$, and for $\Bayes$ and the Gibbs predictor.
\pf By \cref{lem:lengthgadget} and \sref{1}{1}. The $\BP_4$ context has dimension $N_F+1$ and at most
$36N_F^2+1\le36(N_F+1)^2$ examples, and the extra dimension changes $f(3L+2)$ to $f(3L+3)$.
\qedstep{2}{5}
\pf \sref{2}{2}--\sref{2}{4} contradict $\lenETH{C}$.
\end{steps}

\qedstep{1}{5}
\end{steps}
\end{proof}