1
00:00:00,000 --> 00:00:03,000
To make some of the issues, we're going to be talking about simpler.
2
00:00:03,000 --> 00:00:09,000
We're going to focus in on some sense very simple kinds of problems.
3
00:00:09,000 --> 00:00:12,000
Problems that take inputs just like what we've been looking at.
4
00:00:12,000 --> 00:00:18,000
Be the graph or less, whatever happens to be and processes that to get an answer,
5
00:00:18,000 --> 00:00:20,000
and the answer is just 0 or 1, yes or no.
6
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.
7
00:00:25,000 --> 00:00:31,000
An example is graph connectivity where you're given a graph and your ask,
8
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.
9
00:00:36,000 --> 00:00:38,000
It is either connected or it's not connected.
10
00:00:38,000 --> 00:00:43,000
So even though this output is very very simple just 0 or 1 one bit.
11
00:00:43,000 --> 00:00:45,000
It can actually be fairly complicated.
12
00:00:45,000 --> 00:00:51,000
Sometimes very very complicated to take the input and decide whether it is zero or one.
13
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.
14
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?
15
00:01:04,000 --> 00:01:07,000
Another question is given a graph, is it a tree? Yes or no.
16
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.
17
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?
18
00:01:17,000 --> 00:01:22,000
An edge that if it gets removed separates the graph into two separate pieces.
19
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.
20
00:01:28,000 --> 00:01:33,000
That the shortest path between them is no more than K steps.
21
00:01:33,000 --> 00:01:35,000
Now the question is G bipartite.
22
00:01:35,000 --> 00:01:40,000
This was a homework problem or they were a closely related homework problem
23
00:01:40,000 --> 00:01:44,000
where you can take a graph and try to work out whether it is separable
24
00:01:44,000 --> 00:01:49,000
into two sets of nodes with edges only going between the sets.
25
00:01:49,000 --> 00:01:54,000
Now you could argue that in sometimes this problems are a little bit silly.
26
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,
27
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,
28
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,
29
00:02:11,000 --> 00:02:15,000
or can v be reached in fewer than K steps from u?
30
00:02:15,000 --> 00:02:17,000
Well if it can be show me the path.
31
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.
32
00:02:21,000 --> 00:02:26,000
So an interesting fact about decision problems is that they are often directly relatable
33
00:02:26,000 --> 00:02:32,000
to the version of the problem that your interested and that actually gives the answer,
34
00:02:32,000 --> 00:02:39,000
and sometimes you can actually connect them with only a polynomial amount of extra work.
35
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.