On the complexity of trial and error for constraint satisfaction problems

Ivanyos, G; Kulkarni, R; Qiao, Y; Santha, M; Sundaram, A

On the complexity of trial and error for constraint satisfaction problems

Ivanyos, G Kulkarni, R Qiao, Y

Santha, M Sundaram, A

Permalink

Publication Type:: Journal Article
Citation:: Journal of Computer and System Sciences, 2018, 92 pp. 48 - 64
Issue Date:: 2018-03-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript VersionAdobe PDF (499.4 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ivanyos, G	en_US
dc.contributor.author	Kulkarni, R	en_US
dc.contributor.author	Qiao, Y https://orcid.org/0000-0003-4334-1449	en_US
dc.contributor.author	Santha, M	en_US
dc.contributor.author	Sundaram, A	en_US
dc.date.available	2020-05-25T19:03:13Z
dc.date.issued	2018-03-01	en_US
dc.identifier.citation	Journal of Computer and System Sciences, 2018, 92 pp. 48 - 64	en_US
dc.identifier.issn	0022-0000	en_US
dc.identifier.uri	http://hdl.handle.net/10453/130881
dc.description.abstract	© 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.	en_US
dc.relation	http://purl.org/au-research/grants/arc/DE150100720
dc.relation.ispartof	Journal of Computer and System Sciences	en_US
dc.relation.isbasedon	10.1016/j.jcss.2017.07.005	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	On the complexity of trial and error for constraint satisfaction problems	en_US
dc.type	Journal Article
utslib.citation.volume	92	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0806 Information Systems	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	92	en_US

Abstract:

© 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:

http://hdl.handle.net/10453/130881