
To make some of the issues, we're going to be talking about simpler.

We're going to focus in on some sense very simple kinds of problems.

Problems that take inputs just like what we've been looking at.

Be the graph or less, whatever happens to be and processes that to get an answer,

and the answer is just 0 or 1, yes or no.

So that's the sense in which it's making a decision. It's making a yes no decision base on the inputs.

An example is graph connectivity where you're given a graph and your ask,

are all the nodes reachable from all the other nodes in the graph and the answer is either yes or no.

It is either connected or it's not connected.

So even though this output is very very simple just 0 or 1 one bit.

It can actually be fairly complicated.

Sometimes very very complicated to take the input and decide whether it is zero or one.

Here's another example. If I give you a graph and node v and a node u and a number k.

Those are the inputs. The question is can v be reached in fewer than k steps from u?

Another question is given a graph, is it a tree? Yes or no.

For it to be a tree, it needs to be connected and not have any cycles in it. No loops.

Now the decision problem is given a graph, is there a bridge link somewhere in the graph?

An edge that if it gets removed separates the graph into two separate pieces.

Given a graph and a number K. Is there a pair of nodes that are K steps apart.

That the shortest path between them is no more than K steps.

Now the question is G bipartite.

This was a homework problem or they were a closely related homework problem

where you can take a graph and try to work out whether it is separable

into two sets of nodes with edges only going between the sets.

Now you could argue that in sometimes this problems are a little bit silly.

We don't often want to know just one bit of answer, we want to know something like,

is there a pair of nodes K steps apart but find me a pair of nodes K steps apart,

or is the graph bipartite but separated into two pieces and show me what those pieces are,

or can v be reached in fewer than K steps from u?

Well if it can be show me the path.

I really like to know the path cause that's what I'm going to be able to work with.

So an interesting fact about decision problems is that they are often directly relatable

to the version of the problem that your interested and that actually gives the answer,

and sometimes you can actually connect them with only a polynomial amount of extra work.

So basically, if the decision problem is efficient so is the problem that returns the more interesting input.