  Weitzman (1979) introduced the Pandora Box problem as a model for sequential
search with inspection costs, and gave an elegant index-based policy that
attains provably optimal expected payoff. In various scenarios, the searching
agent may select an option without making a costly inspection. The variant of
the Pandora box problem with non-obligatory inspection has attracted interest
from both economics and algorithms researchers. Various simple algorithms have
proved suboptimal, with the best known 0.8-approximation algorithm due to Guha
et al. (2008). No hardness result for the problem was known.
  In this work, we show that it is NP-hard to compute an optimal policy for
Pandora's problem with nonobligatory inspection. We also give a polynomial-time
approximation scheme (PTAS) that computes policies with an expected payoff at
least $(1 - \epsilon)$-fraction of the optimal, for arbitrarily small $\epsilon
> 0$. On the side, we show the decision version of the problem to be in NP.
