[SOUND] [SOUND] We'll communicate with the oracle through a little program. Here it is. We can ask the oracle to guess a pattern, but let's start with something simple. Let's say we want a pattern of length 8 and without any variables; so it's just an 8-bit string. Okay, so the oracle guessed a pattern. Now, it's an 8-bit string; it has no variables. So the language defined by this pattern consists of only one string, and this string is just this pattern itself. There are 2 to 8, that is 256 possible 8-bit strings. One of them is guessed by our oracle, and we want to find out which one. So, initially our version space consists of 256 instances. Let's try membership queries. Maybe, this string is all ones. One, two, three, four, five, six, seven, eight. Is it so? No. Okay, then, maybe, it's all zeros. One, two, three, four, five, six, seven, eight. Again, no. Okay, maybe, there are some ones in the middle. No. Now, let's stop for a second and see what we have learned. Well, initially we had 256 instances in our version space, and what we have done is, essentially, we removed three instances from this version space; so each membership query was answered "no", and it allowed us to exclude exactly one instance from the version space. So now we still have to consider 253 potential binary strings. Well, it looks like membership queries won't get us too far, because, in the worst case, we will continue to be unlucky and get "no" all the time, and then we will have to ask 255 questions. Too many. So let's see if we can use equivalence queries instead. Let's modify our hypothesis a little bit. So let's say, it starts with 1. Is it so? No. But now we got a counterexample. And this counterexample is the same as our hypothesis. So, is it positive or negative? Well, it matches our hypothesis (because it's the same as our hypothesis), and it is a counterexample. So it means that it doesn't match the target pattern, the pattern guessed by the oracle. And so, this must be a negative counterexample. Yeah, but what does it give us? Again, the only thing we have learned is that this is not the string guessed by the oracle. So -1 from our hypothesis space, from our version space. Let's try something more interesting, let's replace this 0 with x and, maybe, this 0 with y. So, again a query, and the answer is "no". Now we got a counterexample. Well, this counterexample is again negative, because it matches our hypothesis, but it doesn't match, but then it doesn't match the target pattern. And again we only removed one example from the version space. So, again, if we continue being unlucky, if we get "no" all the time, and if the oracle gives us negative counterexamples, then all we learn with one equivalence query is that one particular string is not the one guessed by the oracle, but there's an exponential number of other strings, other potential strings. So again this is not very efficient. And it's easy to see that subset query won't give us anything more interesting, because, in a subset query, we will also get negative counterexamples. Subset query always gives us negative counterexamples. And negative counterexamples are not very helpful, as we have seen. So let's try superset query. Let's give it some binary string, for instance, 0011000. Now the answer is "no", and we got a counterexample. But now this counterexample doesn't match our hypothesis. But then it should match the target pattern. But the target pattern is a binary string. And this binary string matches that binary string, so it should be the same. So what I'm saying is that this is the answer. Let's check it. So let's say that this is our hypothesis, and let's ask the equivalence query. And yes, the answer is "yes", so that's what the oracle has guessed. So the upshot is that it is sufficient to issue just one superset query to get the right answer. Either the oracle says "yes", and then we know that the string we submitted is the one it guessed. Or it says "no", but then it has to reveal the string that it has guessed, because the oracle, when it says "no" to a superset query, must provide a positive counterexample. And if its pattern is a binary string without any variables, then it has exactly one positive example, and so it should reveal it. On the other hand, if we don't use superset queries and use only membership, equivalence, and subset queries, it might happen that we have to ask an exponential number of questions, because each query might remove at most one element from the version space. Okay, but this approach with one superset query works only when we have no variables in our pattern and we know the length. Now let's consider the general case. Can we learn a pattern in polynomial time if we don't know the length and if the pattern might contain variables? Let's see it in the next video. [SOUND]