Name
Abstract | ||
|---|---|---|
In 2013 Bei, Chen and Zhang introduced a trial and error model of computing, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if the assignment is not satisfying. In this paper we initiate a systematic study of constraint satisfaction problems in the trial and error model, by adopting a formal framework for CSPs, and defining several types of revealing oracles. Our main contribution is to develop a transfer theorem for each type of the revealing oracle. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another CSP in the normal setting, such that their complexities are polynomial-time equivalent. This in principle transfers the study of a large class of hidden CSPs to the study of normal CSPs. We apply the transfer theorems to get polynomial-time algorithms or hardness results for several families of concrete problems. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.jcss.2017.07.005 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
Trial and error,Constraint satisfaction problems,Computational complexity | Journal | 92 |
ISSN | Citations | PageRank |
0022-0000 | 3 | 0.41 |
References | Authors | |
8 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gábor Ivanyos | 1 | 257 | 28.02 |
| Raghav Kulkarni | 2 | 172 | 19.48 |
| Youming Qiao | 3 | 97 | 15.55 |
| Miklos Santha | 4 | 728 | 92.42 |
| Aarthi Sundaram | 5 | 4 | 3.18 |