Imagen de Portada

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kátay, Tamás, Tóth, László Márton, Vidnyánszky, Zoltán
Formato:	Preprint
Publicado:	2023
Materias:	Logic Computational Complexity 03E25, 68Q17
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Hyperfiniteness on Topological Ramsey Spaces
por: Bursics, Balázs, et al.
Publicado: (2024)

Undefinability of Approximation of 2-to-2 Games
por: Dawar, Anuj, et al.
Publicado: (2025)

Computational Complexity of Model-Checking Quantum Pushdown Systems
por: Lin, Deren, et al.
Publicado: (2025)

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

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

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
por: Larrauri, Alberto
Publicado: (2025)

The Axiom of Choice in the $κ$-Mantle
por: Lietz, Andreas
Publicado: (2024)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
por: Lela, Marko
Publicado: (2025)

On forcing axioms and weakenings of the Axiom of Choice
por: Bomfim, Diego Lima, et al.
Publicado: (2024)

A Gentle Introduction to the Axiom of Choice
por: Blass, Andreas, et al.
Publicado: (2025)

Unifying lower bounds for algebraic machines, semantically
por: Seiller, Thomas, et al.
Publicado: (2018)

A note on Łoś's Theorem without the Axiom of Choice
por: Usuba, Toshimichi
Publicado: (2023)

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
por: Kattermann, David, et al.
Publicado: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
por: Atserias, Albert, et al.
Publicado: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
por: Galatos, Nikolaos, et al.
Publicado: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
por: Asimi, Kristina, et al.
Publicado: (2020)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
por: Bergougnoux, Benjamin, et al.
Publicado: (2025)

Variants of Baumgartner's Axiom for Lipschitz Functions on Baire and Cantor Space
por: Switzer, Corey Bacal
Publicado: (2025)

The complexity of being monitorable
por: Camerlo, Riccardo, et al.
Publicado: (2026)

Finitely Bounded Homogeneity Turned Inside-Out
por: Rydval, Jakub
Publicado: (2021)

Adversarial Barrier in Uniform Class Separation
por: Rosko, Milan
Publicado: (2025)

Uniformity in learning structures
por: Cipriani, Vittorio, et al.
Publicado: (2025)

Classifying different criteria for learning algebraic structures
por: Bazhenov, Nikolay, et al.
Publicado: (2024)

The Category Dichotomy for Ideals
por: Dow, Alan, et al.
Publicado: (2025)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
por: Bodirsky, Manuel, et al.
Publicado: (2024)

Foundational Analysis Of The Solvability Complexity Index: The Weihrauch-SCI Intermediate Hierarchy
por: Sorg, Christopher
Publicado: (2026)

Why the classes P and NP are not well-defined finitarily
por: Anand, Bhupinder Singh
Publicado: (2024)

A Minimal Substitution Basis for the Kalmár Elementary Functions
por: Prunescu, Mihai, et al.
Publicado: (2025)

The equational theory of the Weihrauch lattice with multiplication
por: Neumann, Eike, et al.
Publicado: (2024)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
por: Abdullah, Duaa, et al.
Publicado: (2025)

Constraint satisfaction problems, compactness and non-measurable sets
por: Tardif, Claude
Publicado: (2025)

Flexible constraint satisfiability and a problem in semigroup theory
por: Jackson, Marcel
Publicado: (2015)

Learning Equivalence Relations on Polish Spaces
por: Rossegger, Dino, et al.
Publicado: (2024)

On the learning power of Friedman-Stanley jumps
por: Cipriani, Vittorio, et al.
Publicado: (2025)

Paradox on the Countable Axiom of Choice
por: Nezhad, Babak Jabbar
Publicado: (2024)

Cardinal Well-foundedness and Choice
por: Blass, Andreas, et al.
Publicado: (2023)

Connecting the space of marked groups and the space of group operations
por: Kátay, Tamás
Publicado: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
por: Janaki, V., et al.
Publicado: (2023)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
por: Ye, Lixi
Publicado: (2026)

The Axiom of Double Complement and its opposites
por: Jeon, Hanul, et al.
Publicado: (2026)