complexity of the subgroup problem in free groups
From: Abi (abi_k--cut-here--_at_myrealbox.com)
Date: 07/03/04
- Next message: |-|erc: "Re: Daryl, Dave, Barb and the Georges' source of Confusion"
- Previous message: Rob Duncan: "Re: Infinity can not exist"
- Next in thread: Derek Holt: "Re: complexity of the subgroup problem in free groups"
- Reply: Derek Holt: "Re: complexity of the subgroup problem in free groups"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 03 Jul 2004 15:57:23 +0530
Hi *,
I'd like to know the currently best known complexity to solve the
subgroup problem in free groups.
the problem is as follows.
Let Z be a finite alphabet, and consider the free group G on {Z U Z'}
where Z' is the set of inverses of the elements of Z.
if K is a subset of G, and consider the subgroup generated by {K U K'}
where K' is the set of all the inverses of the words in U. We would
like to test membership in the subgroup of G generated by {K U K'}.
I had read about Nielsen reductions, but all this is going above my
head. I'd like to know the complexity of the best known solution to
this problem. I am trying to know whether it is in NP or not and what
is its complexity class.
Thanks,
abi.
- Next message: |-|erc: "Re: Daryl, Dave, Barb and the Georges' source of Confusion"
- Previous message: Rob Duncan: "Re: Infinity can not exist"
- Next in thread: Derek Holt: "Re: complexity of the subgroup problem in free groups"
- Reply: Derek Holt: "Re: complexity of the subgroup problem in free groups"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
