  One of the fundamental questions of Algorithmic Mechanism Design is whether
there exists an inherent clash between truthfulness and computational
tractability: in particular, whether polynomial-time truthful mechanisms for
combinatorial auctions are provably weaker in terms of approximation ratio than
non-truthful ones. This question was very recently answered for universally
truthful mechanisms for combinatorial auctions \cite{D11}, and even for
truthful-in-expectation mechanisms \cite{DughmiV11}. However, both of these
results are based on information-theoretic arguments for valuations given by a
value oracle, and leave open the possibility of polynomial-time truthful
mechanisms for succinctly described classes of valuations.
  This paper is the first to prove {\em computational hardness} results for
truthful mechanisms for combinatorial auctions with succinctly described
valuations. We prove that there is a class of succinctly represented submodular
valuations for which no deterministic truthful mechanism provides an
$m^{1/2-\epsilon}$-approximation for a constant $\epsilon>0$, unless $NP=RP$
($m$ denotes the number of items). Furthermore, we prove that even
truthful-in-expectation mechanisms cannot approximate combinatorial auctions
with certain succinctly described submodular valuations better than within
$n^\gamma$, where $n$ is the number of bidders and $\gamma>0$ some absolute
constant, unless $NP \subseteq P/poly$. In addition, we prove computational
hardness results for two related problems.
