We will now give a formal definition of a Search Problem. And we will do this by considering the famous boolean satisfiability problem. The input for this problem is a formula in conjunctive normal form, which is usually abbreviated just as CNF. So a formal and conjunctive number form is just a set of clauses. In this case, in this example, we have five clauses. This is the first one. This is the second one. The third one, the fourth one, and the last one. Each clause is a logical, is a logical or, or a disjunction of a few literals. For example, the first one is a disjunction of literals x, y, and z. The second one is the disjunction of x and the negation of y. The third one is a disjunction of y and not z, or a negation of z, and so on. So x, y and z are Boolean variables. These are variables that take Boolean values. The Boolean values are true and false and we will usually use 1 instead of true and 0 instead of false. So what this formula tells us is the first clause actually constrains the values of x, y, and z to be so that either x = 1, or y = 1, or z = 1, right? So this is just x, or y, or z. The second clause tells use that either x must be true, or the negation of y must be true. That is, either x = 1, or y = 0 and so on. For example, the last clause tells us that either x = 0 or y = 0, or z = 0. Then, the Boolean Satisfiability problem, or just Satisfiability problem, which is also abbreviated as SAT usually, is stated as follows. Given a formula in conjunctive normal form, we would like to check whether it is satisfiable or not. That is, whether it is possible to assign Boolean values to all variables so that all clauses are satisfied. If it is possible, we need to output a satisfying assignment. If it is not possible, we need to report that no such assignment exists. Now we give a few examples. In the first example, we're given a formula over two variables, x and y. It contains three clauses, and it is satisfiable. To satisfy it, we can assign the value 1 to x and the value 0 to y. Let's check that it indeed satisfies all three clauses. Well, in the first clause, x is satisfied. In the second clause, not y is satisfied. And, in the last clause X is satisfied. In the second example, we illustrate that a formula may have more than just one satisfying assignment. For example, for this formula there is a satisfying assignment which assigns the value 1 to x, y, and z and there is another satisfying assignment which is shown here. Okay, for the last formula, the last formula is unsatisfiable. And probably the most straightforward way to check this is just to list all possible truth assignments to x, y and z. So there are eight such assignments. Let me list them all. Then for each of these assignments, we need to check that each of them falsifies at least one clause. For example, the first one falsifies the first clause. When x, and y, and z = 0, the first clause is falsified, right? For the second one, it falsifies the clause y or not z, right? The third one falsifies the clause x or naught y and so on. So it can be checked that each of these eight assignments falsifies at least one clause. So another way of showing that this formula is satisfiable is the following. Let's first try to assign the value zero to x. Then let's take a look at the following clause. So it is x or not y. x is already assigned zero. So the only way to satisfy this clause is to assign the value 0 to y. So setting x to 0 forces us to set y to 0 also. Now let's take a look at this clause. It forces us to set the values 0 to z, also. But then we see that this clause is already falsified, right, which tells us that our initial move, I mean to assign 0 to x was a wrong move. That we need to assign the value 1 to x. Let's try to do this. If x = 1, let's take a look at the following clause. Not x is already falsified in this clause, so we need to assign the value 1 to z. Now let's take at this clause. Not z is already falsified here so we need to assign the value 1 to y. But then this clause is falsified. So no matter how we assign x, it forces us to some other assignments and in the end, we falsify some clause which justifies that this formula is unsatisfiable. That is a canonical hard problem. It has applications in various branches of computer science. In particular because many hard combinatorial problems are reduced very easily to the satisfiability problems. I mean, many hard combinatorial problems can be stated very naturally in terms of SAT and then when a problem is stated in terms of SAT, we can use a so-called SAT solver, which is a program that solves the satisfiability problem. There are many such programs and there is even a [INAUDIBLE] competition of SAT solvers. SAT is also a classical example of a so-called search problem. In a search problem, we're given an instance site, or just and and our goal is to final a solution for this instance. A solution S or to report that there is not such solution. For example, in case of the SAT problem, an instance I is a formula in conjunctive normal form and S is a satisfied assignment. For this formula, we need to check whether there is a satisfying assignment and to return one if it exists. Or to report that this formula is unsatisfiable. This is, that there is no satisfying assignment. A natural property to require from a such problem is that we can quickly check with a given Solution S is indeed a solution for I. For example, in case of SAT, it is easy. If we are given a truth assignment of values to all the variables, we can quickly check whether it satisfies all the clauses. Namely, we just count all the clauses from left to right and for each clause, we check whether it contains literal that satisfies this clause. Another natural property is that we require the length of S to be bounded by polynomial in the lengths of I. Right, so we want S to be not very large. We do not want S to have, for example, exponential size in the length of I. In this case, it would require us an exponential time just to write down a solution for the instance I. So once again, the natural property of a search problem is the following. We have an algorithm which checks whether the given solution S is indeed a solution for an instance I in time, which is bounded by polynomial in the lengths of I only. This also forces S, the length of S, to be bounded by a polynomial of I. In fact, it is convenient to define a search problem through such a very fine algorithm. Namely we say that this search problem is defined by an algorithm C that takes two parameter as an input. An instance I and a candidate solution S. It should run in time polynomial I, in the length of I, and we say that S is a solution for the instance I if C of I, S returns true. For example, SAT is clearly a search problem. In this case, once again, I is a CNF formula and S is a truth assignment of Boolean values to variables. And this algorithm, C, just scans all the clauses and checks whether each clause contains a literal that is satisfied by the given assignment, S. Of course, it's surrounding time is polynomial in the lengths of the formula. Great. In the next part, we will see a few examples of search problems that arise frequently in factors for which we still don't know polynomial time algorithms.
