Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FINITE GROUPS:
Reports tagged with finite groups:
TR01-029 | 27th March 2001
Denis Xavier Charles

#### A Note on Subgroup Membership Problem for PSL(2,p).

We show that there are infinitely many primes \$p\$, such
that the subgroup membership problem for PSL(2,p) belongs
to \$\NP \cap \coNP\$.

more >>>

TR02-030 | 3rd June 2002
Lars Engebretsen, Jonas Holmerin, Alexander Russell

#### Inapproximability Results for Equations over Finite Groups

Revisions: 1

An equation over a finite group G is an expression of form
w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted
variable, or a constant from G; such an equation is satisfiable
if there is a setting of the variables to values in G ... more >>>

TR05-005 | 20th December 2004
Tomas Feder

#### Constraint Satisfaction on Finite Groups with Near Subgroups

Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ... more >>>

ISSN 1433-8092 | Imprint