Equation Satisfiability and Program Satisfiablity for Finite Monoids

David Bix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson and Denis ThŽrien

Working Papers from Santa Fe Institute

Abstract: We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [4] by exhibiting quasi-polynomial time algorithms for a sub-class of solvable non-nilpotent groups and relate this question to a natural circuit complexity conjecture.

Keywords: Computational complexity; groups; semigroups; monoids (search for similar items in EconPapers)
Date: 2000-04
References: View complete reference list from CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:00-04-026

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().