1.Previous
3.Next

the input. The output is "yes" when at least one of these solutions is valid, and "no" when none of them are.
# The validity of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a valid solution (if one exists) by trying all possible solutions.
# The problem can be used to simulate every other problem for which we can verify quickly that a solution is valid. Hence, if we could find valid

1.Previous
3.Next