  Constraint satisfaction (CSP) and structure isomorphism (SI) are among the
most well-studied computational problems in Computer Science. While neither
problem is thought to be in $\texttt{PTIME},$ much work is done on
$\texttt{PTIME}$ approximations to both problems. Two such historically
important approximations are the $k$-consistency algorithm for CSP and the
$k$-Weisfeiler-Leman algorithm for SI, both of which are based on propagating
local partial solutions. The limitations of these algorithms are well-known;
$k$-consistency can solve precisely those CSPs of bounded width and
$k$-Weisfeiler-Leman can only distinguish structures which differ on properties
definable in $C^k$. In this paper, we introduce a novel sheaf-theoretic
approach to CSP and SI and their approximations. We show that both problems can
be viewed as deciding the existence of global sections of presheaves,
$\mathcal{H}_k(A,B)$ and $\mathcal{I}_k(A,B)$ and that the success of the
$k$-consistency and $k$-Weisfeiler-Leman algorithms correspond to the existence
of certain efficiently computable subpresheaves of these. Furthermore, building
on work of Abramsky and others in quantum foundations, we show how to use
\v{C}ech cohomology in $\mathcal{H}_k(A,B)$ and $\mathcal{I}_k(A,B)$ to detect
obstructions to the existence of the desired global sections and derive new
efficient cohomological algorithms extending $k$-consistency and
$k$-Weisfeiler-Leman. We show that cohomological $k$-consistency can solve
systems of equations over all finite rings and that cohomological
Weisfeiler-Leman can distinguish positive and negative instances of the
Cai-F\"urer-Immerman property over several important classes of structures.
