Editing Promise problem (section)

==Definition==

A decision problem can be associated with a [[formal language|language]] <math>L \subseteq \{0,1\}^*</math>, where the problem is to accept all inputs in <math>L</math> and reject all inputs not in <math>L</math>. For a promise problem, there are two languages, <math>L_{\text{YES}}</math> and <math>L_{\text{NO}}</math>, which must be [[Disjoint sets|disjoint]], which means <math>L_{\text{YES}} \cap L_{\text{NO}} = \varnothing</math>, such that all the inputs in <math>L_{\text{YES}}</math> are to be accepted and all inputs in <math>L_{\text{NO}}</math> are to be rejected. The set <math>L_{\text{YES}} \cup L_{\text{NO}}</math> is called the ''promise''. There are no requirements on the output if the input does not belong to the promise. If the promise equals <math>\{0,1\}^*</math>, then this is also a decision problem, and the promise is said to be trivial.