Cover Image

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Asimi, Kristina, Barto, Libor, Dalmau, Victor
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
by: Barto, Libor, et al.
Published: (2024)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
by: Barto, Libor, et al.
Published: (2021)

The Rise of Plurimorphisms: Algebraic Approach to Approximation
by: Barto, Libor, et al.
Published: (2024)

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
by: Yamakami, Tomoyuki
Published: (2024)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Local consistency as a reduction between constraint satisfaction problems
by: Dalmau, Victor, et al.
Published: (2023)

The Constraint Satisfaction Problem Over Multisorted Cores
by: Delic, Dejan, et al.
Published: (2025)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
by: Chen, Hubie
Published: (2020)

On Classifying Continuous Constraint Satisfaction Problems
by: Miltzow, Tillmann, et al.
Published: (2021)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
by: DeHaan, Ian, et al.
Published: (2025)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
by: Ciardo, Lorenzo, et al.
Published: (2025)

On the Usefulness of Promises
by: Austrin, Per, et al.
Published: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

Parameterized Complexity of the Star Decomposition Problem
by: Hajebi, Sahab, et al.
Published: (2024)

On the Complexity of Problems on Tree-structured Graphs
by: Bodlaender, Hans L., et al.
Published: (2022)

Towards Solving NP-Complete and Other Hard Problems Efficiently in Practice
by: Digulescu, Mircea-Adrian
Published: (2026)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
by: Istrate, Gabriel
Published: (2024)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
by: Bilò, Davide, et al.
Published: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
by: Jackiewicz, Marcel, et al.
Published: (2024)

The Complexity of Counting Turns in the Line-Based Dial-a-Ride Problem
by: Lauerbach, Antonio, et al.
Published: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)

Ex-post Stability under Two-Sided Matching: Complexity and Characterization
by: Aziz, Haris, et al.
Published: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

On the Descriptive Complexity of Vertex Deletion Problems
by: Bannach, Max, et al.
Published: (2024)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)