Cover Image

Complexity Classification Transfer for CSPs via Algebraic Products

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodirsky, Manuel, Jonsson, Peter, Martin, Barnaby, Mottet, Antoine, Semanišinová, Žaneta
Format:	Preprint
Published:	2022
Subjects:	Logic Computational Complexity Logic in Computer Science 06A05, 68Q25, 08A70 F.4.1; F.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

Polynomial definability in constraint languages with few subpowers
by: Bulín, Jakub, et al.
Published: (2023)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

On the existence of strong proof complexity generators
by: Krajicek, Jan
Published: (2022)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

Universal Algebra in UniMath
by: Amato, Gianluca, et al.
Published: (2021)

Hypersequent Calculi Have Ackermannian Complexity
by: Balasubramanian, A. R., et al.
Published: (2026)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
by: Grochow, Joshua A., et al.
Published: (2022)

Extended Nullstellensatz proof systems
by: Krajicek, Jan
Published: (2023)

Continuous and algebraic domains in univalent foundations
by: de Jong, Tom, et al.
Published: (2024)

Deducibility in the full Lambek calculus with weakening is HAck-complete
by: Greati, Vitor, et al.
Published: (2024)

Behavioural Conformances based on Lax Couplings
by: Wild, Paul, et al.
Published: (2025)

Reversible computations are computations
by: Aubert, Clément, et al.
Published: (2025)

Commutative N-polyregular functions
by: Lopez, Aliaume
Published: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

Arithmetics within the Linear Time Hierarchy
by: Pollett, Chris
Published: (2025)

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

Three Fixed-Dimension Satisfiability Semantics for Quantum Logic: Implications and an Explicit Separator
by: Higuchi, Joaquim Reizi
Published: (2026)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
by: Kazakov, Yevgeny, et al.
Published: (2009)

Descriptive complexity for neural networks via Boolean networks
by: Ahvonen, Veeti, et al.
Published: (2023)

A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
by: Ramos, Arthur, et al.
Published: (2025)

Algebraic Proof Theory for Infinitary Action Logic
by: Fussner, Wesley, et al.
Published: (2025)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

Structure-Guided Automated Reasoning
by: Bannach, Max, et al.
Published: (2023)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

Adversarial Barrier in Uniform Class Separation
by: Rosko, Milan
Published: (2025)

On the Satisfaction Probabilities of $k$-CNF Formulas
by: Tantau, Till
Published: (2022)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)