Equation Satisfiability and Program Satisfiablity for Finite Monoids

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.

MoreLess

Year of publication:	2000-04
Authors:	Barrington, David Bix ; McKenzie, Pierre ; Moore, Cristopher ; Tesson, Pascal ; ThŽrien, Denis
Institutions:	Santa Fe Institute
Subject:	Computational complexity \| groups \| semigroups \| monoids

More details

Series:	Working Papers.
Type of publication:	Book / Working Paper
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10005790799