WEBVTT
00:00:00.000 --> 00:00:03.000
To make some of the issues, we're going to be talking about simpler.
00:00:03.000 --> 00:00:09.000
We're going to focus in on some sense very simple kinds of problems.
00:00:09.000 --> 00:00:12.000
Problems that take inputs just like what we've been looking at.
00:00:12.000 --> 00:00:18.000
Be the graph or less, whatever happens to be and processes that to get an answer,
00:00:18.000 --> 00:00:20.000
and the answer is just 0 or 1, yes or no.
00:00:20.000 --> 00:00:25.000
So that's the sense in which it's making a decision. It's making a yes no decision base on the inputs.
00:00:25.000 --> 00:00:31.000
An example is graph connectivity where you're given a graph and your ask,
00:00:31.000 --> 00:00:36.000
are all the nodes reachable from all the other nodes in the graph and the answer is either yes or no.
00:00:36.000 --> 00:00:38.000
It is either connected or it's not connected.
00:00:38.000 --> 00:00:43.000
So even though this output is very very simple just 0 or 1 one bit.
00:00:43.000 --> 00:00:45.000
It can actually be fairly complicated.
00:00:45.000 --> 00:00:51.000
Sometimes very very complicated to take the input and decide whether it is zero or one.
00:00:51.000 --> 00:00:58.000
Here's another example. If I give you a graph and node v and a node u and a number k.
00:00:58.000 --> 00:01:04.000
Those are the inputs. The question is can v be reached in fewer than k steps from u?
00:01:04.000 --> 00:01:07.000
Another question is given a graph, is it a tree? Yes or no.
00:01:07.000 --> 00:01:12.000
For it to be a tree, it needs to be connected and not have any cycles in it. No loops.
00:01:12.000 --> 00:01:17.000
Now the decision problem is given a graph, is there a bridge link somewhere in the graph?
00:01:17.000 --> 00:01:22.000
An edge that if it gets removed separates the graph into two separate pieces.
00:01:22.000 --> 00:01:28.000
Given a graph and a number K. Is there a pair of nodes that are K steps apart.
00:01:28.000 --> 00:01:33.000
That the shortest path between them is no more than K steps.
00:01:33.000 --> 00:01:35.000
Now the question is G bipartite.
00:01:35.000 --> 00:01:40.000
This was a homework problem or they were a closely related homework problem
00:01:40.000 --> 00:01:44.000
where you can take a graph and try to work out whether it is separable
00:01:44.000 --> 00:01:49.000
into two sets of nodes with edges only going between the sets.
00:01:49.000 --> 00:01:54.000
Now you could argue that in sometimes this problems are a little bit silly.
00:01:54.000 --> 00:01:59.000
We don't often want to know just one bit of answer, we want to know something like,
00:01:59.000 --> 00:02:03.000
is there a pair of nodes K steps apart but find me a pair of nodes K steps apart,
00:02:03.000 --> 00:02:11.000
or is the graph bipartite but separated into two pieces and show me what those pieces are,
00:02:11.000 --> 00:02:15.000
or can v be reached in fewer than K steps from u?
00:02:15.000 --> 00:02:17.000
Well if it can be show me the path.
00:02:17.000 --> 00:02:21.000
I really like to know the path cause that's what I'm going to be able to work with.
00:02:21.000 --> 00:02:26.000
So an interesting fact about decision problems is that they are often directly relatable
00:02:26.000 --> 00:02:32.000
to the version of the problem that your interested and that actually gives the answer,
00:02:32.000 --> 00:02:39.000
and sometimes you can actually connect them with only a polynomial amount of extra work.
00:02:39.000 --> 00:02:46.000
So basically, if the decision problem is efficient so is the problem that returns the more interesting input.