\section{The hardness of Bayesian inference in context}\label{sec:hardness}

The lower bounds rest on one gadget. It turns a CNF into a context that is consistent for every formula,
together with a query whose posterior predictive reveals whether the formula is satisfiable.

\subsection{The gadget}\label{sec:gadget}

\begin{restatable}[Bayes gadget]{lemma}{lembayesgadget}\label[lemma]{lem:bayesgadget}
Let $k\ge1$, and let $F$ be a $k$-CNF on $z_1,\dots,z_n$ with $M$ clauses, none of them tautological. Let
$\Gamma_F$ be the CNF on $z_1,\dots,z_n,a,u$ with the clauses
\[
\neg a\vee C\quad(C\in F),\qquad a\vee\neg z_i\quad(i\in[n]),\qquad a\vee\neg u .
\]
Then $\Gamma_F$ is a $(k+1)$-CNF with $M+n+1$ clauses, none of them tautological. It has $2\#F+1$ satisfying
assignments, and exactly $2\#F$ of them set $a=1$.
\end{restatable}

\begin{proof}[Proof sketch]
If $a=1$, every clause $a\vee\cdot$ holds, the clauses $\neg a\vee C$ reduce to $F$, and $u$ is free: $2\#F$
assignments. If $a=0$, the clauses $\neg a\vee C$ hold and the others force $z=0$ and $u=0$: one assignment
(\cref{app:hardness}).
\end{proof}

A positive example of literal disjunctions is a clause (\cref{ex:local}(a)), and \cref{fact:gadget} turns a
CNF into a sample of binarized perceptrons with the same solutions. The query $e_a$, the unit vector of the
coordinate of $a$, is labeled $1$ exactly by the descriptions with $a=1$, in both classes.

\begin{restatable}[Bayes contexts]{lemma}{lembayescontexts}\label[lemma]{lem:bayescontexts}
Let $k\ge2$, and let $F$ be a $k$-CNF on $n$ variables with $M$ clauses, none of them tautological. One can
compute in polynomial time:
\begin{enumerate}[label=(\alph*)]
\item a context $S^{\LD}_F$ of $M+n+1$ positive examples of $\LD_{k+1}$ in dimension $n+2$, and
\item a context $S^{\BP}_F$ of $M+n+k$ positive examples of $\BP_{2k}$ in dimension $n+k+1$,
\end{enumerate}
both consistent, such that the query $e_a$ has posterior predictive $p_S(e_a)=2\#F/(2\#F+1)$ in both. In
particular $p_S(e_a)=0$ if $F$ is unsatisfiable, $p_S(e_a)\ge2/3$ otherwise, and $\#F=p_S(e_a)/(2(1-p_S(e_a)))$.
\end{restatable}

\begin{proof}[Proof sketch]
For~(a), take the positive examples of the clauses of $\Gamma_F$. For~(b), apply \cref{fact:gadget} to
$\Gamma_F$, a $(k+1)$-CNF, with $p=k-1$ padding coordinates. In both, the version space is in bijection with
the satisfying assignments of $\Gamma_F$, the posterior is uniform on it, and the query is labeled by $a$
(\cref{app:hardness}).
\end{proof}

For the length form of ETH we need locality $3$ and dimension linear in the length of the formula. Splitting
clauses changes the number of solutions, but not whether there is one, and that suffices.

\begin{restatable}[Bayes contexts by length]{lemma}{lemlengthgadget}\label[lemma]{lem:lengthgadget}
Given a CNF $F$ of length $L\ge1$, one can compute in polynomial time a consistent context of positive
examples of $\LD_3$ in dimension $N\le3L+2$, with at most $\min\{5L+1,36N^2\}$ examples, such that the query
$e_a$ has posterior predictive $0$ if $F$ is unsatisfiable and at least $2/3$ otherwise. The same holds for
$\BP_4$ in dimension $N+1$, with one more example.
\end{restatable}

\begin{proof}[Proof sketch]
Split $F$ into an equisatisfiable $3$-CNF $F'$ with at most $2L$ variables and at most $L$ clauses. Replace
each clause $C$ of $F'$ by $\neg a\vee C$ if $|C|\le2$. If $C=\ell_1\vee\ell_2\vee\ell_3$, use a fresh variable
$y_C$ and the clauses $\neg a\vee\ell_1\vee y_C$, $\neg y_C\vee\ell_2\vee\ell_3$ and $a\vee\neg y_C$. Add
$a\vee\neg z$ for every variable $z$ of $F'$ and $a\vee\neg u$. If $a=0$, all variables are forced to $0$,
which satisfies every clause; if $a=1$, the clauses for $C$ have a solution in $y_C$ exactly when $C$ holds,
and $u$ is free. So the branch $a=1$ has no assignment or at least two, and the branch $a=0$ has one
(\cref{app:hardness}).
\end{proof}

\subsection{Lower bounds}\label{sec:lower}

\begin{restatable}[Hardness of Bayesian inference in context]{theorem}{thmhardness}\label{thm:hardness}
\begin{enumerate}[label=(\alph*)]
\item\label{it:seth} Assume \cref{hyp:cnfseth}. For every $\gamma\in(0,1)$ there are $K$ and $c_\gamma$ such
that no randomized algorithm with error probability at most $1/3$ does the following in time
$O(2^{(1-\gamma)N})$: given a consistent context of at most $N^{c_\gamma}$ positive examples of
$\BP_{\lceil K\log N\rceil}$ in dimension $N$ and a query, output a number within $1/4$ of the posterior
predictive. The same holds for $\LD_{\lceil K\log N\rceil}$, for computing $\Bayes(S,x)$, and for running the
Gibbs predictor exactly or within statistical distance $1/6$. Under \cref{hyp:cnfeth}, there are
$K,c_\gamma,\rho>0$ with the same statements for time $O(2^{\rho N})$.
\item\label{it:len} Assume $\lenETH{C}$, and let $\theta>0$. No randomized algorithm with error probability
at most $1/3$ outputs, for every consistent context of at most $36N^2$ positive examples of $\LD_3$ in
dimension $N$ and every query, a number within $1/4$ of the posterior predictive in time
$2^{N/(\log N)^{C+\theta}}$. The same holds for $\BP_4$, for computing $\Bayes(S,x)$, and for running the Gibbs
predictor exactly or within statistical distance $1/6$.
\end{enumerate}
\end{restatable}

\begin{proof}[Proof sketch]
For~\ref{it:seth}, take a $k$-CNF with $k=\lfloor K'\log n\rfloor$ and at most $n^{c'}$ clauses from
\cref{fact:logsat} for $\gamma/2$, and build $S^{\BP}_F$. Its dimension is $N\le n+K'\log n+1$ and its
sparsity is $2k\le K\log N$. A number within $1/4$ of $p_S(e_a)$ is at most $1/4$ if $F$ is unsatisfiable and
at least $5/12$ otherwise, and $\Bayes(S,e_a)=1$ exactly when $F$ is satisfiable. An algorithm in time
$O(2^{(1-\gamma)N})$ would decide the formula in time $O(2^{(1-\gamma/2)n})$. For~\ref{it:len}, use
\cref{lem:lengthgadget}: a time bound $2^{N/(\log N)^{C+\theta}}$ at $N\le3L+2$ is at most $2^{L/(\log L)^C}$ for
large $L$ (\cref{app:hardness}).
\end{proof}

Together with \cref{thm:bayesalg}, the theorem fixes the exponent of Bayesian inference in context at
constant locality, up to polylogarithmic factors.

\begin{corollary}[Bayesian inference in context is SAT by length]\label[corollary]{cor:twosided}
Let $\kappa\ge3$ be a constant. Without noise, Bayesian inference in context for $\kappa$-local classes takes
time $\poly(m)\cdot2^{O(N\log\log N/\sqrt{\log N})}$ for every context length $m$. Under $\lenETH{C}$, for
every $\theta>0$, approximating it within $1/4$ needs time $2^{N/(\log N)^{C+\theta}}$ already for $\LD_3$ on
contexts of at most $36N^2$ examples.
\end{corollary}

\begin{proof}
The upper bound is \cref{thm:bayesalg}\ref{it:noiseless} with $\kappa$ constant, and the lower bound is
\cref{thm:hardness}\ref{it:len}, since $\LD_3$ is $\kappa$-local for every $\kappa\ge3$.
\end{proof}

Exact Bayesian inference in context computes $\#F$ through \cref{lem:bayescontexts}, so it is equivalent to
counting, as consistency is equivalent to satisfiability~\cite[Theorem~3.4]{Li26}.

\begin{restatable}[Bayesian inference in context is $\#\kappa$-SAT]{theorem}{thmbayesequiv}\label{thm:bayesequiv}
Let $k\ge2$, and let $T,T'$ be nondecreasing time bounds.
\begin{enumerate}[label=(\roman*)]
\item If $\#k$-SAT on $n$ variables with $M$ clauses can be solved in time $T(n,M)$, then noiseless Bayesian
inference in context for $k$-local classes with $N$-bit descriptions takes time
$2T(N,(m+1)2^k)+\poly(N,m)\cdot2^k$ on consistent contexts of size $m$.
\item If noiseless Bayesian inference in context for $\BP_{2k}$, on consistent contexts of size $m$ in
dimension $n$, can be done exactly in time $T'(n,m)$, then $\#k$-SAT on $n$ variables with $M$ clauses can be
solved in time $T'(n+k+1,M+n+k)+\poly(n,M)$.
\end{enumerate}
\end{restatable}

\begin{proof}
Part~(i) is \cref{cor:fromcount}. For~(ii), delete tautological clauses, which changes no count, build
$S^{\BP}_F$ by \cref{lem:bayescontexts}, compute $p=p_S(e_a)<1$, and output $p/(2(1-p))$.
\end{proof}

The hard contexts are consistent, so the lower bounds do not come from deciding consistency, which is
trivial for them. They are, however, atypical for the prior: all their labels are positive, and a random
task labels them so only with probability $(2\#F+1)/2^N$. The bounds therefore concern Bayesian inference
in context on every context, the guarantee that the Bayesian explanation of in-context learning attributes
to a trained model, and not the Bayes risk on typical episodes. \Cref{sec:average} treats the latter.