Computational problem
For example, the complexity classes Both instances and solutions are represented by binary strings, namely elements of {0, 1}*.For example, primality testing can be represented as the infinite set In a search problem, the answers can be arbitrary strings.The following is an example of a (decision) promise problem: 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}*.Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.