Re: complexity of the subgroup problem in free groups
From: Derek Holt (mareg_at_warwick.ac.uk)
Date: 07/08/04
- Next message: phil: "Re: Printer Toner Capacity"
- Previous message: Dirk Van de moortel: "Re: A little lesson for sqrt(144) year olds."
- In reply to: Abi: "complexity of the subgroup problem in free groups"
- Next in thread: David Wagner: "Re: complexity of the subgroup problem in free groups"
- Reply: David Wagner: "Re: complexity of the subgroup problem in free groups"
- Messages sorted by: [ date ] [ thread ]
Date: 8 Jul 2004 09:46:36 -0700
Abi <abi_k--cut-here--@myrealbox.com> wrote in message news:<k2wu1ll71w.fsf@vayu.cs.iitm.ernet.in>...
> 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.
What you probably mean is the free group on Z.
(The set of inverses of an arbitrary alphabet does not make much
sense.)
> 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'}.
This is normally described as the subgroup of G generated by 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.
I do not know what the complexity is, but this problem can be solved
very fast in practice. For a given K, you construct a finite state A
for which a reduced word w lies in <K> iff it is in the language of
A.
So, for a fixed K, testing membership of elements of G in K is linear,
but constructing the automaton involves determinization of a
non-deterministic automaton, so it might not be polynomial in general.
Derek Holt.
- Next message: phil: "Re: Printer Toner Capacity"
- Previous message: Dirk Van de moortel: "Re: A little lesson for sqrt(144) year olds."
- In reply to: Abi: "complexity of the subgroup problem in free groups"
- Next in thread: David Wagner: "Re: complexity of the subgroup problem in free groups"
- Reply: David Wagner: "Re: complexity of the subgroup problem in free groups"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
