Buchumschlag

Network Satisfaction Problems Solved by k-Consistency

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodirsky, Manuel, Knäuer, Simon
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Logic Computational Complexity Logic in Computer Science Rings and Algebras
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2025)

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

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

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)

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

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

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

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

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

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

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

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

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
von: Lemke, Caroline, et al.
Veröffentlicht: (2025)

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

An order out of nowhere: a new algorithm for infinite-domain CSPs
von: Mottet, Antoine, et al.
Veröffentlicht: (2023)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
von: Nechesov, Andrey
Veröffentlicht: (2024)

Proof Complexity of Linear Logics
von: Tabatabai, Amirhossein Akbar, et al.
Veröffentlicht: (2026)

Proof complexity of positive branching programs
von: Das, Anupam, et al.
Veröffentlicht: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
von: Ježil, Ondřej, et al.
Veröffentlicht: (2026)

Effective Versions of Strong Measure Zero
von: Rayman, Matthew
Veröffentlicht: (2025)

The complete classification for quantified equality constraints
von: Zhuk, Dmitriy, et al.
Veröffentlicht: (2021)

Meta-Mathematics of Computational Complexity Theory
von: Oliveira, Igor C.
Veröffentlicht: (2025)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
von: Atserias, Albert, et al.
Veröffentlicht: (2024)

Solving promise equations over monoids and groups
von: Larrauri, Alberto, et al.
Veröffentlicht: (2024)

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

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

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

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

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

On the Descriptive Complexity of Vertex Deletion Problems
von: Bannach, Max, et al.
Veröffentlicht: (2024)

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

On the Complexity of the Skolem Problem at Low Orders
von: Bacik, Piotr, et al.
Veröffentlicht: (2025)

Universal Horn Sentences and the Joint Embedding Property
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2021)

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

Finite Variable Counting Logics with Restricted Requantification
von: Raßmann, Simon, et al.
Veröffentlicht: (2024)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
von: Blanc, Manon, et al.
Veröffentlicht: (2023)

Measuring robustness of dynamical systems. Relating time and space to length and precision
von: Blanc, Manon, et al.
Veröffentlicht: (2023)

On Probabilistic and Causal Reasoning with Summation Operators
von: Ibeling, Duligur, et al.
Veröffentlicht: (2024)