In computer science a decision problem is a set of related problem instances, such that every problem instance requires a YES/NO answer. A typical example of a decision problem is the question: "Is a given integer prime? One instance of this decision problem would be "Is 17 prime?". |
In computer science a decision problem is a set of related problem instances, such that every problem instance requires a YES/NO answer. A typical example of a decision problem is the question: "Is a given integer prime?" One instance of this decision problem would be "Is 17 prime?". |
* The strings over {'a', 'b'} that conists of alternating a's and b's. * The strings over {'a', 'b'} that contain an equal amount of a's and b's. * The strings that describe a graph whith edges labeled with natural numbers indicating their length, and and a path in that graph such that it is the shortes path between its begin and end node. |
* The strings over {a, b} that conists of alternating a's and b's. * The strings over {a, b} that contain an equal amount of a's and b's. * The strings that describe a graph with edges labeled with natural numbers indicating their length, two vertices of the graph, and a path in the graph which is the shortest path between the two vertices. |