  In this paper we introduce constructible analogs of the discrete complexity
classes $\mathbf{VP}$ and $\mathbf{VNP}$ of sequences of functions. The
functions in the new definitions are constructible functions on $\mathbb{R}^n$
or $\mathbb{C}^n$. We define a class of sequences of constructible functions
that play a role analogous to that of $\mathbf{VP}$ in the more classical
theory. The class analogous to $\mathbf{VNP}$ is defined using Euler
integration. We discuss several examples, develop a theory of completeness, and
pose a conjecture analogous to the $\mathbf{VP}$ vs. $\mathbf{VNP}$ conjecture
in the classical case. In the second part of the paper we extend the notions of
complexity classes to sequences of constructible sheaves over $\mathbb{R}^n$
(or its one point compactification). We introduce a class of sequences of
simple constructible sheaves, that could be seen as the sheaf-theoretic analog
of the Blum-Shub-Smale class $\mathbf{P}_{\mathbb{R}}$. We also define a
hierarchy of complexity classes of sheaves mirroring the polynomial hierarchy,
$\mathbf{PH}_{\mathbb{R}}$, in the B-S-S theory. We prove a singly exponential
upper bound on the topological complexity of the sheaves in this hierarchy
mirroring a similar result in the B-S-S setting. We obtain as a result an
algorithm with singly exponential complexity for a sheaf-theoretic variant of
the real quantifier elimination problem. We pose the natural sheaf-theoretic
analogs of the classical $\mathbf{P}$ vs. $\mathbf{NP}$ question, and also
discuss a connection with Toda's theorem from discrete complexity theory in the
context of constructible sheaves. We also discuss possible generalizations of
the questions in complexity theory related to separation of complexity classes
to more general categories via sequences of adjoint pairs of functors.
