So what is this mysterious SAT problem?
So SAT stands for Boolean satisfiability,
of course, that also doesn't tell you very much,
but I'll soon get into what Boolean satisfiability is.
You have to just note that SAT is one of the
most famous and most studied problems in theoretical computer science,
and it's the bases of many marked results,
so it's always a good idea to familiarize yourself with what SAT is about
and why SAT can be so hard to solve.
So what is the Boolean satisfiability problem?
The input for SAT is a so called Boolean formula,
and that actually sounds much more intimidating than it is
because Boolean formulas are very simple structures.
They consist of only 4 building blocks.
As any kind of formula, we have variables,
and those variables I'll write in this course usually as X1, X2, X3, and so on.
And the nice thing about these variables is
so in a normal formula whenever you have
X that can take a number of different values,
but in a Boolean formula,
a variable X can only take 2 different values.
It can either be true, which is sometimes also written as a 1
or it can be false, which is sometimes also written as a 0.
The second thing you can have in a Boolean formula is
an operator called not.
And how you write that is, if you say,
have a variable X1, then this here would be not X1
or if you have X2, this here would be not X2,
and what the not does is it turns a true into a false,
and vice versus, so it also turns a false into a true.
So for example, if X1 equals true,
then not X1 equals false.
So it basically just flips that variable.
Then you have another operator, and that one is called and.
And this and is usually written like this,
and it works on 2 variables, so you have X1 and X2
or any other variable.
And the way it works is that
this expression here, X1 and X2
is true only if X1 is true
and X2 is true.
Otherwise, it's always false.
So I'm going to write this as 1s and 0s here just to make it a bit shorter,
but you know that 1 stands for true and 0 stands for false,
so it's the same.
So 0 and 0 equals 0,
0 and 1 equals 0,
1 and 0 equals 0,
and only 1 and 1 equals 1.
And the final component of a Boolean formula
is another operator called or,
and or is written just the other way around,
so it's written like a flipped and.
So it's X1 or X2,
and as the name already suggests,
that is set to true or set to 1
if at least 1 of these variables here is set to true,
so 0 or 0, that will still be 0,
but 0 or 1 will be 1,
1 or 0 will be 1,
and 1 or 1 is also going to evaluate to 1.
So let's practice this in a little quiz.
Let's say you have the following Boolean formula.
X1 or not X2 or X3 and not X1 or X2,
and we're going to have that X1 is equal to true or 1,
X2 is equal to true,
and X3 is also set to true or 1.
Is this whole formula equal to true or is it equal to false?
So please select this button here if you
think the whole formula is equal to false or 0,
and please select this one here if the whole
formula is equal to true or 1.