On the complexity of trial and error
Xiaohui Bei, Ning Chen, Shengyu Zhang · 2013
Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems in which inputs are unknown. More specifically, we consider constraint satisfaction problems ⋀i Ci, where the constraints Ci are hidden, and the goal is to find a solution satisfying all constraints. We can adaptively propose a candidate solution (i.e., trial), and there is a verification oracle that either confirms that it is a valid solution, or returns the index i of a violated constraint (i.e., error), with the exact content of Ci still hidden.