Property-restricting computational problems

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 groups described by encodings, groups described by presentations, representations of groups), and we are asked to determine whether the structures are isomorphic.

Given a subgroup property $p$ , 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 $p$ .

One satisfies certificate problem: This is an isomorphism testing problem that works given the certificate that a particular one of them satisfies the property $p$ .

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 $p$ . What we must guarantee is that if they both satisfy $p$ , we should solve the isomorphism problem.