2-SAT

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

291 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

291 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

Coping with NP-completeness

After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We first show that some special cases on NP-complete problems can, in fact, be solved in polynomial time. We then consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.

2-SAT: Algorithm12:24

Independent Sets in Trees14:05

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

In this lesson, we will consider all of the reasons

that solve NP-complete problems in special cases.

The main message of this lesson is the following.

The fact that your problem is NP-complete does not exclude a possibility of a very

efficient algorithm that solves your problem in some special restrictive cases.

So once again, the fact that the problem is NP-complete means that it is difficult

to design an efficient algorithm that works for all possible cases.

But it might be the case that for

some special cases there exists a much more efficient algorithm.

Our first example of such a problem is 2-satisfiability problem.

For this problem, we will see a surprising connection between boolean formulas

in 2-CNF and graphs.

Namely, we will apply the depth-first search algorithm to

solve a special case of the satisfiability problem just in linear time.

The input of the 2-satisfiability problem, which is also abbreviated as just 2-SAT,

is a set of clauses, each of which contains at most two literals.

Recall that the literal is a boolean variable or

a negation of a boolean variable.

And what we need to find is to check whether we can assign boolean

values to the variables of this formula to satisfy all these clauses.

So what we need to return is as I said a satisfying assignment or

we need to report that there is no such satisfying assignment.

Let me give you a few two examples.

So this is a formula in 2-CNF.

So all clauses contain at most two literals and

it can be satisfied with the following assignment.

Let's check it.

If x = 0, y = 1 and z = 0, so that means of course,

the first clause is satisfied by the literal y which has value 1.

The second clause is satisfied by the negation of z, so

z has value 0, so negation of z has value 1.

And finally, the last clause is satisfied by the negation of x, okay?

This is another formula in 2-CNF and it is unsatisfiable.

To see this, know that we have to closest of links one here, so

this is the first such clause and it forces us to assign the value 0.

So z must be equal to 0 if we would like to satisfy this formula.

Similarly we need to assign the value 0 to y because of the last clause, right?

Then what is left is these two clauses.

Y and z, the literals y and z are already falsified in these two clauses.

So essentially what is left in this clause is in the first clause we have x,

in the second clause, we have not x.

And of course,

it is not possible to suggest [INAUDIBLE] these clauses by assigning x.

Okay, so this formula is unsatisfiable.

The last example is also an unsatisfiable formula where we

have two variables and it is not difficult to see that this is also unsatisfiable.

Just because these four clauses

actually forbid all four possible ways of assigning the values x and y.

For example, if we try to assign the value 1 to x and the value 0 to y.

Then we get the following clause, so which one?

This one, which is unsatisfied.

And no matter how we assign two values for these two variables,

we always get an unsatisfied clause.

Consider two clause of our input formula.

Say it contains letters l1 and l2.

Basically what it says is that we should not assign similar

[INAUDIBLE] value 0 to both l1 and l2.

Because in this case, this clause will be clearly falsified.

In other words, if we assign the value 0 to l1, we must assign the value 1 to l2.

Because this is the only way to satisfy this clause when l1 is already equal

to zero and vice-versa.

If we assign the value zero to l2, we must assign the value 1 to l1.

So this is the kind of implication and in fact,

implication is a well-known binary operation.

It is defined by the following truth table.

So it is equal to 1 in all cases except for the following one.

When x is equal to 1 and y is equal to 0,

the implication from x to y is also equal to 0.

In all other cases it is equal to 1.

What it does with y is, it says the following,

that falsity implies everything.

It is shown here.

If x if false, then it implies both the truth and the falsity.

However, if x is true,

it only implies the truth.

The implication from x to y when x is equal to 1 is only

equal to 1 when y is equal to 1 too.

This observation brings us to the following so-called implication graph.

It is defined as follows, given a 2-CNF formula,

for each variable of this formula, we introduced two vertices.

One labeled with this variable and one labeled with its negation.

Then for each two clause that contains two literals, say l1 and

l2, we introduce two directed edges.

The first one goes from the negation of l1 to l2 and

the second one goes from the negation of l2 to l1, okay?

And finally for each clause of length one, which contains just some literal l.

We introduce an edge, a directed edge again,

that goes from the negation of l to the l itself.

Okay, so in a sense this graph contains all

implications that I imposed by our input formula.

To give an example, consider the following 2-CNF formula.

Consisting of three variables, x, y, z and four clauses of length two.

To construct each implication graph, we first introduce six vertices,

two vertices for eachiInput variable.

This gives us the following six vertices, x nought x, y nought y, and z nought z.

Then we start introduce edges.

The first clause gives us the following two edges, namely an edge from x to y,

this edge and the next from nought y to nought x.

Once again, it corresponds to the following clause.

Let's understand once again why these two edges correspond to this clause.

Well, what essentially is this

clause says is, is that if not x = 0,

which means that x is equal to 1,

then y must be equal to 1.

This is essentially what is given to us by this implication, right?

It says that if x is 1, then this also must be 1 to satisfy this implication.

The other edge says that if this edge,

if not y = 1, this actually means that y = 0,

then not x must be equal to 1.

And this is indeed true, if y = 0,

then this literal is falsified in this clause.

Which means that the only way to satisfy it is to set not x to be equal to 1,

right?

Then we can continue in the same manner.

For the second clause, we introduce the following two edges.

For the set clause, we introduce the following two edges.

And finally for the last clause, for

the first one, we introduce the following two edges.

Now we have an implication graph.

Now we can see that some specific assignment of boolean values to

the variables of this formula.

For example, when x is equal to 1, y is equal to 1 and z is equal to 1,

all the clauses are satisfied.

It can be easily seen just by observing that each

clause in our input formula contains a positive literal.

By saying positive I mean a variable with no negation.

So for example here, y satisfies this clause here, z satisfies this clause here,

x satisfies this clause and the last clause is satisfied by z and y.

Also we can see that each edge in this graph is also in a sense satisfied.

Now let's consider and as our assignment, that actually falsifies the input formula.

If we assign the value 0 to x, y and

z, then the first three clauses are satisfied.

The first one is satisfied by x, the second one by not y,

the third one by not z, but in the last clause, both the literals are equal to 0.

Okay, and

we see also that the corresponding two edges in the graph are also falsified.

By saying falsified I mean that they are the beginning of this edge has value 1.

So z is equal to 0, so not z is equal to 1.

While the end of this edge is equal to 0, right?

So, one does does not imply 0.

So truth does not imply falsity.

And the same for this edge.

In this case, y = 0, so this vertex has value 1.

While the end of this edge has the value 0.

And this is exactly the situation when the implication is falsified,

when it says that the truth implies falsity.

Now our goal then, given this graph,

our goal is to assign the values to all the variables.

So if our input formula, so that all the edges are satisfied.

And that's we discussed already.

An edge is satisfied if and only if, well,

it is easier to say what it means for an edge to be falsified.

An edge is falsified, when its beginning is labeled with 1 and

its end is labeled with 0.

So we need an assignment to all the variables of our

input formula such that no edge is falsified.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play