On the complexity of trial and error for constraint satisfaction problems
作者：
Highlights：
• A systematic study of the trial and error complexity (introduced by Bei, Chen and Zhang) for constraint satisfaction problems
• For each revealing oracle, a hidden CSP is associated with a normal CSP so that their complexities are polynomially equivalent
• This suggests that the study of CSPs in the trial and error setting can be in principle transferred to normal CSPs
• The transfer theorems are applied to various concrete problems to yield efficient algorithms or hardness results
摘要
•A systematic study of the trial and error complexity (introduced by Bei, Chen and Zhang) for constraint satisfaction problems•For each revealing oracle, a hidden CSP is associated with a normal CSP so that their complexities are polynomially equivalent•This suggests that the study of CSPs in the trial and error setting can be in principle transferred to normal CSPs•The transfer theorems are applied to various concrete problems to yield efficient algorithms or hardness results
论文关键词：Trial and error,Constraint satisfaction problems,Computational complexity
论文评审过程：Received 24 October 2016, Revised 4 June 2017, Accepted 21 July 2017, Available online 13 November 2017, Version of Record 13 November 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.07.005
