Decision Problems

To keep things simple, we will mainly concern ourselves with decision problems. These problems only require a single bit output: ``yes'' and ``no''.

How would you solve the following decision problems?

• Is this directed graph acyclic?

• Is there a spanning tree of this undirected graph with total weight less than w?

• Does this bipartite graph have a perfect (all nodes matched) matching?

• Does the pattern p appear as a substring in text t?