Promise problem

In computational complexity theory, it is usually implicitly assumed that any string in {0, 1}^* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}^* represent valid instances, and one specifies a proper subset of {0, 1}^* as the set of "valid instances". Computational problems of this type are called promise problems.

The following

1.Previous
3.Next