On the complexity of trial and error for constraint satisfaction problems

Publication Type:
Journal Article
Citation:
Journal of Computer and System Sciences, 2018, 92 pp. 48 - 64
Issue Date:
2018-03-01
Filename Description Size
OCC-133918_AM.pdfAccepted Manuscript Version499.4 kB
Adobe PDF
Full metadata record
© 2017 Elsevier Inc. 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.
Please use this identifier to cite or link to this item: