The complexity of equivalence and isomorphism of systems of equations over finite groups

DOI10.1016/J.TCS.2005.07.018MaRDI QIDQ2575758zbMATH OpenOpenAlexFDO

Authors Gustav Nordh

Publication date 6 December 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.07.018

zbMATH Keywords

Computational complexityFinite groupsGraph isomorphismSystems of equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Recommendations

• Mathematical Foundations of Computer Science 2004
• The complexity of solving equations over finite groups
• Solving a fixed number of equations over finite groups
• Computing and Combinatorics
• The complexity of the equation solvability and equivalence problems over finite groups

Cites work

• scientific article; zbMATH DE number 1332670 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• scientific article; zbMATH DE number 1834675 (Why is no real title available?)
• scientific article; zbMATH DE number 233957 (Why is no real title available?)
• A note on the graph isomorphism counting problem
• Computing and Combinatorics
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• On truth-table reducibility to SAT
• STACS 2004
• The Formula Isomorphism Problem
• The complexity of solving equations over finite groups

Cited in

(6)

• Cost of equivalence relations and groups
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• Dichotomies in the complexity of solving systems of equations over finite semigroups
• Mathematical Foundations of Computer Science 2004
• The complexity of the equation solvability problem over semipattern groups

This page was built for publication: The complexity of equivalence and isomorphism of systems of equations over finite groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575758)