Computational Problem - Promise Problems

Promise Problems

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 is an example of a (decision) promise problem:

"Given a graph G, determine if every independent set in G has size at most 5, or G has an independent set of size at least 10."

Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.

Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. The valid instances are those in Lyes ∪ Lno. Lyes and Lno represent the instances whose answer is yes and no, respectively.

Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.

Read more about this topic:  Computational Problem

Famous quotes containing the words promise and/or problems:

    “The parent who loves his child dearly but asks for nothing in return might qualify as a saint, but he will not qualify as a parent. For a child who can claim love without meeting any of the obligations of love will be a self-centered child and many such children have grown up in our time to become petulant lovers and sullen marriage partners because the promise of unconditional love has not been fulfilled.”
    —Selma H. Fraiberg (20th century)

    “I have said many times, and it is literally true, that there is absolutely nothing that could keep me in business, if my job were simply business to me. The human problems which I deal with every day—concerning employees as well as customers—are the problems that fascinate me, that seem important to me.”
    —Hortense Odlum (1892–?)