I don't really understand why promise problems are classified differently than decision problems.

Consider this problem as an example. Given some real number between $0$ and $1$, determine if it greater than $\frac{1}{2}$ or not.

In this problem, that the real number is between $0$ and $1$. Let's say our alphabet is $\{0, 1, 2\}$. Then we can say that our input is encoded like so:

$0$ represents $0$, $1$ represents $\frac{1}{2}$, and $2$ represents $1$

From these 3 cases, we can define any input to represent

$$ \frac{1}{n} \sum_{i=1}^{n} R(x_i) $$

where $x_i$ represents the letter at index $i$ of the input, and $R$ is the transformation that takes $0$ to $0$, $1$ to $\frac{1}{2}$, and $2$ to $1$.

So what is the need to define "Promise-Problems?"


1 Answer 1


In the example you've given it's simple to encode inputs such that they must satisfy the promise. However, in many cases it's hard to do that. Look at the following promise problem, for example: given a SAT instance which has either 0 or 1 solutions, return YES iff it has a single solution.

If there is some encoding for that promise which has polynomial length, can produce all possible inputs for the problem, and can be parsed in polynomial time, then for a given SAT instance, you could add a single trivial solution to it, and an encoding which produces that would be a coNP certificate for the SAT instance, which is impossible assuming $\text{NP}\neq\text{coNP}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.