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 unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems inputs unknown. More specifically, consider constraint satisfaction ⋀i Ci, where constraints Ci hidden, goal is find solution satisfying all constraints. We can adaptively candidate (i.e., trial), there verification oracle that either confirms it valid solution, returns index i violated error), with exact content still hidden.We studied time trial complexities number natural CSPs, summarized as follows. On one hand, despite seemingly very little information provided oracle, efficient algorithms do exist for Nash, Core, Stable Matching, SAT problems, whose unknown-input versions shown be hard corresponding known-input up factor polynomial. The techniques employed vary considerably, including, e.g., order theory ellipsoid method strong separation oracle.On other substantially increased model. In particular, no time-efficient Graph Isomorphism Group (unless PH collapses P = NP). proofs use quite nonstandard reductions, an simulator carefully designed simulate desirable but computationally unaffordable oracle.Our investigates value input information, our results demonstrate lack introduce levels extra difficulty. accommodates wide range combinatorial algebraic structures, exhibits intimate connections (and hopefully also serve useful supplement to) existing learning complexity theories.