Buchumschlag

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodirsky, Manuel, Bonnet, Édouard, Semanišinová, Žaneta
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Logic Computational Complexity 68Q25, 08A70 F.4.1; F.2.2
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Complexity Classification Transfer for CSPs via Algebraic Products
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2022)

The Complexity of Resilience for Digraph Queries
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2026)

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

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
von: Grochow, Joshua A., et al.
Veröffentlicht: (2021)

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

Polynomial definability in constraint languages with few subpowers
von: Bulín, Jakub, et al.
Veröffentlicht: (2023)

Complexities of Well-Quasi-Ordered Substructural Logics
von: Galatos, Nikolaos, et al.
Veröffentlicht: (2025)

Count-Free Weisfeiler--Leman and Group Isomorphism
von: Collins, Nathaniel A., et al.
Veröffentlicht: (2022)

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

Induced Disjoint Paths Without an Induced Minor
von: Aboulker, Pierre, et al.
Veröffentlicht: (2025)

The Word Problem for Products of Symmetric Groups
von: Simon, Hans U.
Veröffentlicht: (2025)

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

Answering Related Questions
von: Bonnet, Édouard
Veröffentlicht: (2025)

Coloring Hardness on Low Twin-Width Graphs
von: Bonnet, Édouard
Veröffentlicht: (2025)

On the Satisfaction Probabilities of $k$-CNF Formulas
von: Tantau, Till
Veröffentlicht: (2022)

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
von: Kazakov, Yevgeny, et al.
Veröffentlicht: (2009)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
von: Xia, Mingji
Veröffentlicht: (2026)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

Hypersequent Calculi Have Ackermannian Complexity
von: Balasubramanian, A. R., et al.
Veröffentlicht: (2026)

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

Parallel Algorithms for Group Isomorphism via Code Equivalence
von: Levet, Michael
Veröffentlicht: (2026)

Group Order Logic
von: Dahan, Anatole
Veröffentlicht: (2025)

Solutions of Word Equations over Partially Commutative Structures
von: Diekert, Volker, et al.
Veröffentlicht: (2016)

Locality, Consistency, and the Tractability Frontier
von: Simas, Tristan
Veröffentlicht: (2026)

A Complexity Dichotomy in Spatial Reasoning via Ramsey Theory
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2020)

Adversarial Barrier in Uniform Class Separation
von: Rosko, Milan
Veröffentlicht: (2025)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
von: Lela, Marko
Veröffentlicht: (2025)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
von: Wulf, Lasse
Veröffentlicht: (2025)

Deducibility in the full Lambek calculus with weakening is HAck-complete
von: Greati, Vitor, et al.
Veröffentlicht: (2024)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
von: Grochow, Joshua A., et al.
Veröffentlicht: (2022)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
von: von Liechtenstein, Maximilian R. P.
Veröffentlicht: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

Extended Nullstellensatz proof systems
von: Krajicek, Jan
Veröffentlicht: (2023)

ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics
von: Haak, Anselm, et al.
Veröffentlicht: (2026)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
von: Oliveria, Mateus de Oliveira, et al.
Veröffentlicht: (2026)

Computational Complexity of Determining the Assembly Index
von: Masierak, Piotr
Veröffentlicht: (2026)

A Bisimulation-Invariance-Based Approach to the Separation of Polynomial Complexity Classes
von: Bruse, Florian, et al.
Veröffentlicht: (2026)

On the existence of strong proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2022)

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