On the complexity of trial and error for constraint satisfaction problems

Ivanyos, Gábor and Kulkarni, R. and Qiao, Y.M. and Santha, M. and Sundaram, A. (2018) On the complexity of trial and error for constraint satisfaction problems. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 92. pp. 48-64. ISSN 0022-0000

Preview

Text 1406.5336.pdf Download (334kB) | Preview

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. (C) 2017 Elsevier Inc. All rights reserved.

Actions (login required)

Edit Item