Journal article icon

Journal article

Beyond PCSP(1-in-3, NAE)

Abstract:

The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists using the strict constraints, the task is to find a solution using the weak constraints. While there are by now several dichotomy results for fragments of PCSPs, they all...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.1016/j.ic.2022.104954

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Jesus College
Role:
Author
ORCID:
0000-0002-0263-159X
Publisher:
Elsevier Publisher's website
Journal:
Information and Computation Journal website
Volume:
289
Issue:
Part A
Article number:
104954
Publication date:
2022-09-05
Acceptance date:
2022-08-28
DOI:
EISSN:
1090-2651
ISSN:
0890-5401
Language:
English
Keywords:
Pubs id:
1276331
Local pid:
pubs:1276331
Deposit date:
2022-08-28

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP