Injective hardness condition for PCSPs

Abstract

We present a template for the Promise Constraint Satisfaction Problem (PCSP) which is NP-hard but does not satisfy the current state-of-the-art hardness condition [ACMTCT'21]. We introduce a new "injective" condition based on the smooth version of the layered PCP Theorem and use this new condition to confirm that the problem is indeed NP-hard. In the second part of the article, we establish a dichotomy for Boolean PCSPs defined by templates with polymorphisms in the set of linear threshold functions. The reasoning relies on the new injective condition.

To be published in LICS'24

References in corpus (8)

• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Algebraic approach to promise constraint satisfaction
• The complexity of promise SAT on non-Boolean domains
• CLAP: A New Algorithm for Promise CSPs
• The complexity of 3-colouring $H$-colourable graphs
• Conditional Dichotomy of Boolean Ordered Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• Injective hardness condition for PCSPs

Cited by in corpus (1)

• Injective hardness condition for PCSPs