Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with finite groups:
TR01-029 | 27th March 2001
Denis Xavier Charles

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

Comments: 1

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