Copertina

Satisfiability of commutative vs. non-commutative CSPs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bulatov, Andrei A., Živný, Stanislav
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Logic in Computer Science Quantum Physics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

Solving promise equations over monoids and groups
di: Larrauri, Alberto, et al.
Pubblicazione: (2024)

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

Discrete Homotopy and Promise Constraint Satisfaction Problem
di: Beikmohammadi, Arash, et al.
Pubblicazione: (2025)

Modular Counting CSP: Reductions and Algorithms
di: Kazeminia, Amirhossein, et al.
Pubblicazione: (2025)

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

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

Existence and nonexistence of commutativity gadgets for entangled CSPs
di: Culf, Eric, et al.
Pubblicazione: (2025)

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

The Rise of Plurimorphisms: Algebraic Approach to Approximation
di: Barto, Libor, et al.
Pubblicazione: (2024)

Non-commutative linear logic fragments with sub-context-free complexity
di: Nishimiya, Yusaku, et al.
Pubblicazione: (2025)

SAT, Gadgets, Max2XOR, and Quantum Annealers
di: Ansótegui, Carlos, et al.
Pubblicazione: (2024)

Quantum First-Order Logics That Capture Logarithmic-Time/Space Quantum Computability
di: Yamakami, Tomoyuki
Pubblicazione: (2025)

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
di: González-Castillo, Samuel, et al.
Pubblicazione: (2026)

The Ideal Membership Problem and Abelian Groups
di: Bulatov, Andrei A., et al.
Pubblicazione: (2022)

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

Probabilistic and Causal Satisfiability: Constraining the Model
di: Bläser, Markus, et al.
Pubblicazione: (2025)

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

Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
di: Colledan, Andrea, et al.
Pubblicazione: (2024)

Solving Satisfiability Modulo Counting for Symbolic and Statistical AI Integration With Provable Guarantees
di: Li, Jinzhao, et al.
Pubblicazione: (2023)

A Schematic Definition of Quantum Polynomial Time Computability
di: Yamakami, Tomoyuki
Pubblicazione: (2018)

Local structure of idempotent algebras I
di: Bulatov, Andrei A.
Pubblicazione: (2020)

The Computational Complexity of Satisfiability in State Space Models
di: Alsmann, Eric, et al.
Pubblicazione: (2025)

Transformer Encoder Satisfiability: Complexity and Impact on Formal Reasoning
di: Sälzer, Marco, et al.
Pubblicazione: (2024)

Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
di: Dawar, Anuj, et al.
Pubblicazione: (2026)

Approximation algorithms for noncommutative CSPs
di: Culf, Eric, et al.
Pubblicazione: (2023)

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

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

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

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

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

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)

The complete classification for quantified equality constraints
di: Zhuk, Dmitriy, et al.
Pubblicazione: (2021)

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)

Local structure of idempotent algebras II
di: Bulatov, Andrei A.
Pubblicazione: (2020)

The NPA hierarchy does not always attain the commuting operator value
di: Fanizza, Marco, et al.
Pubblicazione: (2025)

Local vs. Global Interpretability: A Computational Complexity Perspective
di: Bassan, Shahaf, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable k-CSPs: V
di: Bhangale, Amey, et al.
Pubblicazione: (2024)