Buchumschlag

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodirsky, Manuel, Jahn, Moritz, Konečný, Matěj, Knäuer, Simon, Winkler, Paul
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Rings and Algebras Computational Complexity Logic
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Network Satisfaction Problems Solved by k-Consistency
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Graph Homomorphisms and Universal Algebra
von: Bodirsky, Manuel
Veröffentlicht: (2026)

Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

Datalog-Expressibility for Monadic and Guarded Second-Order Logic
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2020)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
von: Zhuk, Dmitriy
Veröffentlicht: (2024)

The complexity of finding coset-generating polymorphisms and the promise metaproblem
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2026)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
von: Feller, Roman, et al.
Veröffentlicht: (2024)

Conservative Maltsev Constraint Satisfaction Problems
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

Structures preserved by primitive actions of $S_ω$
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

Spectrahedral Shadows and Completely Positive Maps on Real Closed Fields
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2022)

Polynomial-time Tractable Problems over the $p$-adic Numbers
von: Fehm, Arno, et al.
Veröffentlicht: (2025)

When Darwin met Ianus: dichotomies of expressivity
von: Brunar, Johanna, et al.
Veröffentlicht: (2025)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

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

Singleton algorithms for the Constraint Satisfaction Problem
von: Zhuk, Dmitriy
Veröffentlicht: (2025)

Undecidability and incompleteness in quantum information theory and operator algebras
von: Goldbring, Isaac
Veröffentlicht: (2024)

Discrete Homotopy and Promise Constraint Satisfaction Problem
von: Beikmohammadi, Arash, et al.
Veröffentlicht: (2025)

Forbidden Tournaments and the Orientation Completion Problem
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Local structure of idempotent algebras I
von: Bulatov, Andrei A.
Veröffentlicht: (2020)

The Ideal Membership Problem and Abelian Groups
von: Bulatov, Andrei A., et al.
Veröffentlicht: (2022)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

New Perspectives on Semiring Applications to Dynamic Programming
von: Baril, Ambroise, et al.
Veröffentlicht: (2025)

Complex to Rational Fast Matrix Multiplication
von: Moran, Yoav, et al.
Veröffentlicht: (2026)

Formalizing Mason-Stothers Theorem and its Corollaries in Lean 4
von: Baek, Jineon, et al.
Veröffentlicht: (2024)

On Supernilpotent Algebras
von: Wires, Alexander
Veröffentlicht: (2017)

The Constraint Satisfaction Problem Over Multisorted Cores
von: Delic, Dejan, et al.
Veröffentlicht: (2025)

Almost free modules, perfect decomposition and Enochs's conjecture
von: Cortés-Izurdiaga, Manuel, et al.
Veröffentlicht: (2024)

The Descriptive Complexity of Relation Modification Problems
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Semi-abelian by Design: Johnstone Algebras Unifying Implication and Division
von: Forsman, David
Veröffentlicht: (2025)

The Proof Analysis Problem
von: Arteche, Noel, et al.
Veröffentlicht: (2025)

Formalizing Gröbner Basis Theory in Lean
von: Guo, Junyu, et al.
Veröffentlicht: (2026)

On the structure of approximate rings
von: Krupiński, Krzysztof, et al.
Veröffentlicht: (2026)

The Equational Theories Project: Advancing Collaborative Mathematical Research at Scale
von: Bolan, Matthew, et al.
Veröffentlicht: (2025)

A quasi-optimal lower bound for skew polynomial multiplication
von: Chen, Qiyuan, et al.
Veröffentlicht: (2024)

Notes on CSPs and Polymorphisms
von: Brady, Zarathustra
Veröffentlicht: (2022)

Limits of structures and Total NP Search Problems
von: Ježil, Ondřej
Veröffentlicht: (2023)

Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
von: Barto, Libor, et al.
Veröffentlicht: (2021)

Formalizing a classification theorem for low-dimensional solvable Lie algebras in Lean
von: del Barco, Viviana, et al.
Veröffentlicht: (2025)

Some applications of finite BL-algebras
von: Flaut, Cristina, et al.
Veröffentlicht: (2025)