The Complexity of theA B CProblem

DOI10.1137/S0097539794276853MaRDI QIDQ4507329zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Richard J. Lipton, Yechezkel Zalcstein

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794276853

zbMATH Keywords

commutative linear semigroupsJordan normal formsmembership problempolynomial-time algorithms

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Algebraic systems of matrices (15A30) Free semigroups, generators and relations, word problems (20M05) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40)

Recommendations

• The complexity of some complementation problems
• The complexity of satisfiability problems
• On a complexity of the formula \((A\bigvee B) \Rightarrow C\)
• The complexity of minimal satisfiability problems
• scientific article; zbMATH DE number 1688380
• The complexity of constraint satisfaction revisited
• On the complexity of certain completion problems
• scientific article; zbMATH DE number 1072533
• The complexity of two problems on arithmetic circuits
• The complexity of recursive constraint satisfaction problems

Cited in

(11)

• Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem
• scientific article; zbMATH DE number 871949 (Why is no real title available?)
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• REACHABILITY PROBLEMS FOR PRODUCTS OF MATRICES IN SEMIRINGS
• Knapsack and the power word problem in solvable Baumslag–Solitar groups
• On the Monniaux problem in abstract interpretation
• On the Monniaux problem in abstract interpretation
• On the decidability of monadic second-order logic with arithmetic predicates
• On the existential theory of the reals enriched with integer powers of a computable number
• On large zeros of linear recurrence sequences
• Complexity of problem \(TF2|v=1,c=2|C_{\max}\)

This page was built for publication: The Complexity of theA B CProblem

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