On the complexity of trial and error for constraint satisfaction problems

DOI10.1016/J.JCSS.2017.07.005MaRDI QIDQ1678168zbMATH OpenOpenAlexFDO

Authors Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

Publication date 14 November 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.5336, http://hdl.handle.net/10453/130881

zbMATH Keywords

computational complexityconstraint satisfaction problemstrial and error

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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 {em systematic} study of constraint satisfaction problems in the trial and error model. To achieve this, we first adopt a formal framework for CSPs, and based on this framework we define several types of revealing oracles. Our main contribution is to develop a emph{transfer theorem} for each type of the revealing oracle, under a broad class of parameters. To any hidden CSP with a specific type of revealing oracle, the transfer theorem associates another, potentially harder 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, possibly with a promise on the instances, to the study of CSPs in the normal setting. We then apply the transfer theorems to get polynomial-time algorithms or hardness results for hidden CSPs, including satisfaction problems, monotone graph properties, isomorphism problems, and the exact version of the Unique Games problem. Most of the proofs of these results are short and straightforward, which exhibits the power of the transfer theorems.

Recommendations

• On the complexity of trial and error for constraint satisfaction problems
• The complexity of constraint satisfaction revisited
• On the efficient approximability of constraint satisfaction problems
• The approximability of constraint satisfaction problems
• Complexity and approximability of quantified and stochastic constraint satisfaction problems
• The complexity of recursive constraint satisfaction problems
• Constraint satisfaction -- algorithms and complexity analysis
• Parameterized complexity of constraint satisfaction problems
• Tractability in constraint satisfaction problems: a survey

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Noncrossing Subgraphs in Topological Layouts
• On Restricted Two-Factors
• On the complexity of trial and error
• On the complexity of trial and error for constraint satisfaction problems
• On the power of unique 2-prover 1-round games
• Solving linear programming with constraints unknown
• The complexity of satisfiability problems

Cited in

(2)

• On the complexity of trial and error for constraint satisfaction problems
• On the complexity of trial and error

This page was built for publication: On the complexity of trial and error for constraint satisfaction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678168)