Copertina

The complete classification for quantified equality constraints

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Zhuk, Dmitriy, Martin, Barnaby, Wrona, Michal
Natura:	Preprint
Pubblicazione:	2021
Soggetti:	Computational Complexity Logic in Computer Science Logic
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Singleton algorithms for the Constraint Satisfaction Problem
di: Zhuk, Dmitriy
Pubblicazione: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
di: Zhuk, Dmitriy
Pubblicazione: (2024)

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

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

Model-checking positive equality free logic on a fixed structure (direttissima)
di: Bodirsky, Manuel, et al.
Pubblicazione: (2024)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2024)

Arity hierarchies for quantifiers closed under partial polymorphisms
di: Dawar, Anuj, et al.
Pubblicazione: (2025)

Proof complexity of positive branching programs
di: Das, Anupam, et al.
Pubblicazione: (2021)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
di: Nechesov, Andrey
Pubblicazione: (2024)

Proof Complexity of Linear Logics
di: Tabatabai, Amirhossein Akbar, et al.
Pubblicazione: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
di: Mottet, Antoine, et al.
Pubblicazione: (2023)

The Proof Analysis Problem
di: Arteche, Noel, et al.
Pubblicazione: (2025)

Parallelism and Adaptivity in Student-Teacher Witnessing
di: Ježil, Ondřej, et al.
Pubblicazione: (2026)

Effective Versions of Strong Measure Zero
di: Rayman, Matthew
Pubblicazione: (2025)

Meta-Mathematics of Computational Complexity Theory
di: Oliveira, Igor C.
Pubblicazione: (2025)

On the consistency of stronger lower bounds for NEXP
di: Thapen, Neil
Pubblicazione: (2025)

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

Restricted CSPs and F-free Digraph Algorithmics
di: Guzmán-Pro, Santiago, et al.
Pubblicazione: (2025)

A characterization of efficiently compilable constraint languages
di: Berkholz, Christoph, et al.
Pubblicazione: (2023)

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

Complexity classification of counting graph homomorphisms modulo a prime number
di: Bulatov, Andrei A., et al.
Pubblicazione: (2021)

Quasi Directed Jonsson Operations Imply Bounded Width (For fo-expansions of symmetric binary cores with free amalgamation)
di: Wrona, Michal
Pubblicazione: (2024)

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

On Probabilistic and Causal Reasoning with Summation Operators
di: Ibeling, Duligur, et al.
Pubblicazione: (2024)

Measuring Decidability as Related to Busy Beaver Numbers
di: Tandi, Gurpreet, et al.
Pubblicazione: (2026)

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

Measuring robustness of dynamical systems. Relating time and space to length and precision
di: Blanc, Manon, et al.
Pubblicazione: (2023)

On the local consequence of modal Product logic: standard completeness and decidability
di: Vidal, Amanda
Pubblicazione: (2023)

Verifying Quantized Graph Neural Networks is PSPACE-complete
di: Sälzer, Marco, et al.
Pubblicazione: (2025)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
di: Meijer, Lucas, et al.
Pubblicazione: (2025)

Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete
di: Ghosh, Avijeet, et al.
Pubblicazione: (2025)

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

Kleene algebra with commutativity conditions is undecidable
di: de Amorim, Arthur Azevedo, et al.
Pubblicazione: (2024)

Temporal Team Semantics Revisited
di: Gutsfeld, Jens Oliver, et al.
Pubblicazione: (2021)

Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
di: Beyersdorff, Olaf, et al.
Pubblicazione: (2021)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
di: Lemke, Caroline, et al.
Pubblicazione: (2025)

On the Number of Quantifiers Needed to Define Boolean Functions
di: Carmosino, Marco, et al.
Pubblicazione: (2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
di: Chen, Lijie, et al.
Pubblicazione: (2024)

Hardness of monadic second-order formulae over succinct graphs
di: Gamard, Guilhem, et al.
Pubblicazione: (2023)