Group factorization problem - Revision history

Vipul: 5 revisions

2008-05-07T23:39:18Z

5 revisions

← Older revision	Revision as of 23:39, 7 May 2008
(No difference)

Vipul: /* Equivalent decision problems */

2007-02-27T09:11:43Z

Equivalent decision problems

← Older revision		Revision as of 09:11, 27 February 2007
Line 23:		Line 23:
	===Equivalent decision problems===		===Equivalent decision problems===

	* [[Coset ~~intrsection~~ problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.		* [[Coset intersection problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.

	The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.		The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.

Vipul: /* Equivalent decision problems */

2007-02-27T09:11:32Z

Equivalent decision problems

← Older revision		Revision as of 09:11, 27 February 2007
Line 23:		Line 23:
	===Equivalent decision problems===		===Equivalent decision problems===

	* [[Coset ~~itnersection~~ problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.		* [[Coset intrsection problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.

	The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.		The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.

Vipul: /* Equivalent decision problems */

2007-02-27T09:11:16Z

Equivalent decision problems

← Older revision		Revision as of 09:11, 27 February 2007
Line 23:		Line 23:
	===Equivalent decision problems===		===Equivalent decision problems===

	* [[Coset ~~equality~~ problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.		* [[Coset itnersection problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.

	The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.		The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.

Vipul at 09:10, 27 February 2007

2007-02-27T09:10:35Z

← Older revision		Revision as of 09:10, 27 February 2007
Line 29:		Line 29:
	* [[Double coset membership testing problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets, and elements <math>g</math> and <math>h</math> are given. We need to check whether <math>h</math> is in <math>HgK</math>.		* [[Double coset membership testing problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets, and elements <math>g</math> and <math>h</math> are given. We need to check whether <math>h</math> is in <math>HgK</math>.

	The group factorization problem reduces to double coset membership testing simply by setting <math>g</math> to be the identity element. The reduction the other way is a little more tricky.		The group factorization problem reduces to double coset membership testing simply by setting <math>g</math> to be the identity element. The reduction the other way is a little more tricky: it uses the fact that <math>x_1 \in Hx_2K</math> if and only iff <math>x_2^{-1}x_1 \in H^{x_2}K</math>, which is a group factorization.

Vipul at 15:18, 23 February 2007

2007-02-23T15:18:52Z

New page

{{decision problem}}

{{embedding-setup problem}}

==History==

The '''group factorization problem''' was introduced by Hoffmann in his paper ''Group-theoretic methods in graph isomorphism'' published in 1982. Hoffmann showed that graph isomorphism was a special case of a problem called the [[double coset membership testing problem]] and studied a whole class of problems (including the group factorization problem) that are Turing-equivalent to the double coset membership testing problem.

==Description==

===Given data===

Our universe is some group <math>U</math> (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group <math>G</math> in <math>U</math> is specified by a generating set <math>A</math>, and subgroups <math>H</math> and <math>K</math> of <math>G</math> are specified by means of generating sets <math>B</math> and <math>C</math> respectively. An elements <math>h</math> in <math>G</math> is given (described as an element of <math>U</math>).

===Goal===

Determine whether <math>h</math> is in <math>HK</math>.

==Relation with other problems==

===Equivalent decision problems===

* [[Coset equality problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets. An element <math>x</math> in <math>G</math> is given, and we need to determine whether <math>Hx</math> intersects <math>K</math> nontrivially.

The coset equality problem is equivalent to the group factorization problem because saying that <math>Hx</math> intersects <math>K</math> nontrivially is equivalent to saying that <math>x^{-1}</math> is in <math>KH</math>.

* [[Double coset membership testing problem]]: Here, two subgroups <math>H</math> and <math>K</math> are specified by means of generating sets, and elements <math>g</math> and <math>h</math> are given. We need to check whether <math>h</math> is in <math>HgK</math>.

The group factorization problem reduces to double coset membership testing simply by setting <math>g</math> to be the identity element. The reduction the other way is a little more tricky.