Cover Image

On the complexity of solving equations over the symmetric group $S_4$

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aichinger, Erhard, Grünbacher, Simon
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Rings and Algebras 08A40, 68Q25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polynomial interpolation of partial functions in finite algebras with a Mal'cev term
by: Aichinger, Erhard, et al.
Published: (2026)

Polynomial-Time Algorithms for Black-Box Distributive Expanded Groups
by: Anokhin, Mikhail
Published: (2025)

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

Clonoids over vector spaces
by: Fioravanti, Stefano, et al.
Published: (2026)

Polynomial definability in constraint languages with few subpowers
by: Bulín, Jakub, et al.
Published: (2023)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

Zero testing and equation solving for sparse polynomials on rectangular domains
by: Aichinger, Erhard, et al.
Published: (2023)

On when the union of two algebraic sets is algebraic
by: Aichinger, Erhard, et al.
Published: (2023)

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

Polynomial-time isomorphism test for groups with abelian Sylow subgroups
by: Skresanov, Saveliy V.
Published: (2026)

Polynomial-time isomorphism test for $k$-generated extensions of abelian groups
by: Skresanov, Saveliy V.
Published: (2026)

Compression with wildcards: All models of a Boolean 2-CNF
by: Wild, Marcel
Published: (2012)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Conservative Maltsev Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2025)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

Ivo G. Rosenberg's Work on Maximal Clones and Minimal Clones
by: Szendrei, Agnes
Published: (2024)

Barriers for rectangular matrix multiplication
by: Christandl, Matthias, et al.
Published: (2020)

Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity
by: Ham, Lucy, et al.
Published: (2022)

Linear average-case complexity of algorithmic problems in groups
by: Olshanskii, Alexander, et al.
Published: (2022)

On the Low Weight Polynomial Multiple Problem
by: Ţiplea, Ferucio Laurenţiu, et al.
Published: (2024)

There Are No Post-Quantum Weakly Pseudo-Free Families in Any Nontrivial Variety of Expanded Groups
by: Anokhin, Mikhail
Published: (2023)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

On polynomial completeness properties of finite Mal'cev algebras
by: Rossi, Bernardo
Published: (2023)

Clonoids between modules
by: Mayr, Peter, et al.
Published: (2023)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

On the computation of tensor functions under tensor-tensor multiplications with linear maps
by: Ju, Jeong-Hoon, et al.
Published: (2025)

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Computing bases in Hermite normal form of lattices of integer relations
by: Labahn, George, et al.
Published: (2026)

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

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

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

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Symmetric subrank and its border analogue
by: Biaggi, Benjamin, et al.
Published: (2026)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

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

Recognition of Seifert fibered spaces with boundary is in NP
by: Jackson, Adele
Published: (2023)