  Pandora's problem is a fundamental model in economics that studies optimal
search strategies under costly inspection. In this paper we initiate the study
of Pandora's problem with combinatorial costs, capturing many real-life
scenarios where search cost is non-additive. Weitzman's celebrated algorithm
[1979] establishes the remarkable result that, for additive costs, the optimal
search strategy is non-adaptive and computationally feasible.
  We inquire to which extent this structural and computational simplicity
extends beyond additive cost functions. Our main result is that the class of
submodular cost functions admits an optimal strategy that follows a fixed,
non-adaptive order, thus preserving the structural simplicity of additive cost
functions. In contrast, for the more general class of subadditive (or even XOS)
cost functions, the optimal strategy may already need to determine the search
order adaptively. On the computational side, obtaining any approximation to the
optimal utility requires super polynomially many queries to the cost function,
even for a strict subclass of submodular cost functions.
