Vipul: 1 revision

2008-05-08T00:05:27Z

1 revision

← Older revision	Revision as of 00:05, 8 May 2008
(No difference)

Vipul at 11:55, 28 February 2007

2007-02-28T11:55:09Z

New page

==Description==

===Basic idea of restriction===

The scenario is as follows: we have a computational or decision problem that takes as input certain structures (sch as a [[group]], a group along with a [[subgroup]], a [[graph]], a [[representation]]). The general computational problem is the one where we are not given any promises about additional nice properties the structures may satisfy.

Since the general computational problem may be hard, we hope to obtain a simpler computational problem by making restrictive assumptions on the nature of the structures involved. For instance, we may restrict the situation to the case where the groups involved are Abelian, or to the case where the graph involved is a tree, and so on. We would like to know how we can use the restricted version to solve the original problem.

===Two aspects===

There are actually two aspects to solving the property-restricted version of a computational problem.

* Assuming that we are given a ''guarantee'' that the objects involved have the required properties, how do we solve the problem?
* How do we ''recognize'' that the objects involved do have the property?

Typically, only when we can both recognize the property (that is, test for it) and solve easily if the property is satisfied, is the restricted version of use.

==Examples==

===Isomorphism problems===

Here, we are given two structures (these could be [[group]]s described by encodings, [[group]]s described by [[presentation]]s, [[representation]]s of groups), and we are asked to determine whether the structures are isomorphic.

Given a subgroup property <math>p</math>, we define the following problems:

* ''Both satisfy certificate problem'': This is an isomorphism testing problem that works given the certificate that both objects actually satisfy property <math>p</math>.

* ''One satisfies certificate problem'': This is an isomorphism testing problem that works given the certificate that a particular one of them satisfies the property <math>p</math>.

* ''Certificate-free problem'': Here, we are not given any certificates. Rather, we are supposed to use a property test to figure out for each whether it satisfies <math>p</math>. What we must guarantee is that ''if'' they both satisfy <math>p</math>, we should solve the isomorphism problem.

Property-restricting computational problems - Revision history

Vipul: 1 revision

Vipul at 11:55, 28 February 2007