Editing Promise problem (section)

==Examples==
Many natural problems are actually promise problems. For instance, consider the following problem: Given a [[directed acyclic graph]], determine if the graph has a [[path (graph theory)|path]] of length 10. The ''yes'' instances are directed acyclic graphs with a path of length 10, whereas the ''no'' instances are directed acyclic graphs with no path of length 10. The promise is the set of directed acyclic graphs. In this example, the promise is easy to check. In particular, it is very easy to check if a given graph is cyclic. However, the promised property could be difficult to evaluate. For instance, consider the problem "Given a [[Hamiltonian graph]], determine if the graph has a [[cycle (graph theory)|cycle]] of size 4." Now the promise is [[NP-hard]] to evaluate, yet the promise problem is easy to solve since checking for cycles of size 4 can be done in polynomial time.