On the complexity of trial and error
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractMotivated 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 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. We studied the time and trial complexities of a number of natural CSPs, summarized as follows. On one hand, despite the seemingly very little information provided by the oracle, efficient algorithms do exist for Nash, Core, Stable Matching, and SAT problems, whose unknown-input versions are shown to be as hard as the corresponding known-input versions up to a factor of polynomial. The techniques employed vary considerably, including, e.g., order theory and the ellipsoid method with a strong separation oracle. On the other hand, there are problems whose complexities are substantially increased in the unknown-input model. In particular, no time-efficient algorithms exist for Graph Isomorphism and Group Isomorphism (unless PH collapses or P = NP). The proofs use quite nonstandard reductions, in which an efficient simulator is carefully designed to simulate a desirable but computationally unaffordable oracle. Our model investigates the value of input information, and our results demonstrate that the lack of input information can introduce various levels of extra difficulty. The model accommodates a wide range of combinatorial and algebraic structures, and exhibits intimate connections with (and hopefully can also serve as a useful supplement to) certain existing learning and complexity theories. Copyright 2013 ACM.
All Author(s) ListBei X., Chen N., Zhang S.
Name of Conference45th Annual ACM Symposium on Theory of Computing, STOC 2013
Start Date of Conference01/06/2013
End Date of Conference04/06/2013
Place of ConferencePalo Alto, CA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by Joan Feigenbaum,\n\nTo ORKTS: The authors are listed alphabetically according to the convention of the community of theoretical computer
Pages31 - 40
LanguagesEnglish-United Kingdom
KeywordsComplexity, Constraint satisfaction problem, Query, Trial and error, Unknown input

Last updated on 2020-25-10 at 00:40