On the Complexity of Trial and Error
  Motivated by certain applications from physics, biochemistry, economics, and
computer science, in which the objects under investigation are not accessible
because of various limitations, we propose a trial-and-error model to examine
algorithmic issues in such situations. Given a search problem with a hidden
input, we are asked to find a valid solution, to find which we can propose
candidate solutions (trials), and use observed violations (errors), to prepare
future proposals. In accordance with our motivating applications, we consider
the fairly broad class of constraint satisfaction problems, and assume that
errors are signaled by a verification oracle in the format of the index of a
violated constraint (with the content of the constraint still hidden).
  Our discoveries are summarized as follows. On one hand, despite the seemingly
very little information provided by the verification oracle, efficient
algorithms do exist for a number of important problems. For the Nash, Core,
Stable Matching, and SAT problems, the unknown-input versions are as hard as
the corresponding known-input versions, up to a factor of polynomial. We
further give almost tight bounds on the latter two problems' trial
complexities. On the other hand, there are problems whose complexities are
substantially increased in the unknown-input model. In particular, no
time-efficient algorithms exist (under standard hardness assumptions) for Graph
Isomorphism and Group Isomorphism problems. The tools used to achieve these
results include order theory, strong ellipsoid method, and some non-standard
reductions.
  Our model investigates the value of information, and our results demonstrate
that the lack of input information can introduce various levels of extra
difficulty. The model exhibits intimate connections with (and we hope can also
serve as a useful supplement to) certain existing learning and complexity
theories.
