3-SAT to Independent Set

Loading...

Из курса от партнера University of California San Diego

Advanced Algorithms and Complexity

291 оценки

University of California San Diego

Advanced Algorithms and Complexity

291 оценки

Курс 5 из 6 — Specialization Data 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.

Из урока

NP-complete Problems

Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Showing NP-completeness6:40

Independent Set to Vertex Cover5:28

3-SAT to Independent Set14:57

SAT to 3-SAT7:04

Circuit SAT to SAT12:01

All of NP to Circuit SAT5:42

Using SAT-solvers14:11

Познакомьтесь с преподавателями

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

We now come to a more interesting reduction that connects Boolean logic

to graphs.

Namely we are going to reduce this 3-SAT [INAUDIBLE] problem,

there is an independent set problem.

Recall that in the 3-SAT problem,

our input is a formula in 3-CNF, that is a collection of clauses.

Each clause is a disjunction of at most three literals.

And our goal is to check whether it is possible to assign Boolean values

to all the variables of the formula F, so that to satisfy all the given clauses.

Since we need to reduce this to the independent set problem our goal

is to polynomial logarithm that takes the formula F in 3-CNF.

And outputs a graph G and an integer b such that

the input formula F is satisfiable, if and only if,

there is an independent set of size at least b in the graph G.

Before the sign in, this reduction let's recall what does it mean to satisfy

a given formula in conjunctive normal form.

This essentially means that we need to assign a Boolean value to each variable

of the given formula such that each clause contains at least one satisfied literal.

The given example, consider the following formula.

It is satisfied by an assignment which assigns the value true as value 1 to

all the variables.

Indeed, in the first clause we have just all

the literals in the first clause are satisfied.

In the second clause, the first literal is satisfied by this truth assignment.

And in the last clause,

the first literal is also satisfied by this truth assignment.

Then with another assignment that satisfies the same formula,

namely if I assign the value 1 to x and the value 0 to y and z.

We satisfy the first literal in the first clause,

we satisfy both literals in the second clause, and

we satisfy the last literal in the last clause.

This point of view gives us an alternative definition of the satisfiability problem.

Namely to satisfy a given CNF formula, we need to select from each clause

of a given formula one literal, such as the resulting said of selected.

Literals is consistent, meaning that it doesn't contain a literal L,

together with its negation.

Let me illustrate this on a toy example, as usual.

Assume that we have a formula consistent of three clauses over variables x,

y, and z.

Well by consistent set of literals in this case, we mean for example x, x and not z.

So this is one, so from first clause we select the literal x, from the second one

we also select the literal x, and from the third clause we select the literal not z.

Note that for these consistent set of literals,

we can find the corresponding satisfying assignment.

Namely, we assign value 1 to x, and the value 0 to z.

Namely, we satisfy all the literal in this set.

So for this we assign the value 1 to x and value 0 to z.

It is easy to see that this is indeed a satisfying assignment.

So in the first clause x is satisfied on the second clause,

x is satisfied on the last clause not z inside this fight.

It was the value of y doesn't actually matter in this case.

We can get a the full consistent set of literal just by selecting x and

from the first clause x from the second clause, and y from the third clause.

And as a possibility is to select x from the first one,

not y from the second one and not z from the third one.

This will give us the following constant set of literals.

Once again, we want this set of literals to be consistent so

that we are able to assign a specific value for reach literal.

So for this, to explain this better

let's consider some inconsistent sets of literals.

Assume that from the first clause we select not y,

from the second clause we select the negation of y from the second,

from the third clause we select not z.

So this gives us the following set of literals,

which is inconsistent because It contains was y and a negation of y.

In this case, we can not assign

the value to y to satisfy all the laterals in this clause.

Namely if we assigns a value 0 to y, then we falsify this literal y.

If we assign the value 1 to y, we falsify this literal in this clause.

And this is exactly the reason why we would like our set of selected literals

to be consistent.

This alternative statement of the satisfiability problem is the main idea,

is the main ingredient of our reduction from 3-SAT to

the independent set problem problem.

We illustrate the reduction first on a toy example as usual.

Given a formula in this case with five clauses,

so with three variables, x y and z.

The first step is to introduce for each clause two or

three new vertices labeled with the literals of this clause.

In this case, it gives us the following picture.

So x, y and z here correspond to this clause.

X and not y here respond to this clause the last

three vertices to respond to this clause and so on.

The next thing to do is to join all the vertices,

all the pairs of vertices inside each block.

So for those three clauses, we have two triangles and

for those two clauses, we have just three edges.

Once again, each three clause corresponds to a triangle,

each two clause, that is clause of length two corresponds to a single edge.

So all these edges actually, what am I going to do,

is to find a large independent set in this graph.

And all the newly added edges force us to

select into our independent set at most one vertex from each block.

For example we cannot select two vertices from this block you aren't

doing independent set because any two of them are joined by an edge.

The same is for this block, for example.

We can only select just one vertex from this block into an independent set,

because they are connected by en edge.

So selecting a vertex from each of these blocks into an independent set,

corresponds to selecting a literal from the corresponding clause,

that is going to be satisfied in this clause.

We call that in each clause we need to select a literal which is going to satisfy

this clause.

So we mimic this by selecting the corresponding vertex from a block.

However, recall that we need to select a consistent set of literals.

That is we do not want to select for example,

was x from some clause and not x from some other clause.

To force our set of selected vertices to

be labeled with consistent set of literals,

we just add all possible edges between all pairs of complementary literals.

Namely, whenever we have a vertex labeled with x like this one, and

not x kike this one, we join them by an edge.

So we have x here, we have not x here, we join them by an edge.

Another pair of vertices x here and not x here.

We also join them by an edge, then there is another vertex labeled by x,

we'll also join them by an edge, x and not x and z this not x.

And we do this for all of the pairs of complementary literals.

Now, the claim is that this graph contains an independent set of sides.

Exactly 5 or at least 5 if and only if the initial formula is satisfiable.

And it is already clear, so if the formula is satisfiable,

this means that for each clause we can select one literal

such that the resulting set of literals is consistent.

But this also means that from each of these five block, so

this is the first block, corresponding to the first block, this is the second,

this is the third one, this is the fourth one, this is the fifth one.

We can select exactly the same vertex that corresponds to the selected

literal in this formula.

So if the formula is satisfiable, then in each block we can select on vertex.

And we know that they are not going to be joined by edges,

because vertices from different blocks are only joined if they are complementary.

And we know that our set of literals does not contain complimentary literals.

So if the formula is satisfiable,

then this graph contains an independent set of size 5.

And vice versa uses graph contents an independent set of size 5 and

the formula is satisfied both.

Why is that?

Well just because any independent set of size 5

has exactly 1 various of nature of these blocks.

And we know that the labels of these vertices give us a set of

literals which is consistent, which doesn't contain

a literal together with it's complementary literal.

So it gives us a set of literals such that it

intersects every clause of our initial formula.

Which means that if the response,

they are satisfying the assignment of the initial formula.

To summarize, let's state this reduction formally.

The reduction works as follows, given formula F in 3-CNF, that is

a collection of clauses, each of length at most three, what is the following?

We scan the set of the clauses from left to right and

for each clause, we introduce three or two,

or just one dependent on the number of literals in this clause.

Three or two, or one vertices, and we'll label them with

literals of this clause and we join every two of them by an edge.

So we are now constructing a graph G, and

this forces every independent set in this graph to contain

at most one vertex from each block to responding to a single clause.

Then we also need to force each independent set to be labeled with

a set of literals which is consist.

For this we do the following, we join every pair of vertices

in our graph which are labeled with complementary literals.

That is if I got axis labeled with a literal L, we add new addresses

that connect it to all vertices, which are labeled with a negation of L.

Then what we've just proved on it, our example is the following.

The resulting graph G contains an independent set of size B,

where B is the number of clauses of the initial formula

even though with the initial formula is satisfiable.

It remains to note that the running time of

the resulting transformation is polynomial.

Why is that?

Well just because to construct this graph we first just

scan the formula which takes linear time on the size of the formula.

It is just big O of the number of clauses,

to make it more formal let's denote by m the number of clauses and

in our formula then this step takes time O(m).

We just count the list of clauses and during this scan we introduce 3m vertices.

And then we need to check every pair of these vertices and to join them by

intersect if they're labeled by a complimentary pair of literals.

So the second step clearly takes time at most m squared.

In any case, this is polynomial so the wall transformation takes polynomial time.

Formally, we need also to describe an algorithm that transforms

any solution to the maximum independent set problem for

the resulting graph back to a solution to the three satisfiability problem.

And we also need to ensure that if there is no solution for

the resulting instance of the maximum independent set problems,

then there is no solution for the initial problem.

But this is not difficult, and we did this already.

Namely, if there is a solution for the resulting

instance of the maximum independent set problem and there is a maximum,

there is an independent set of size equal to the number of clauses.

That means that from each block we can select a vertex,

such that all the labels of these vertices is consistent.

If the consistent set of literals, but this also means that this gives

the satisfying assignment of the initial formula.

If on the other hand, there is no solution for the resulting instance of

the independent set problem, then we know that the initial formula is unsatisfiable.

Indeed if it were satisfiable, if there were a satisfying assignment for

the initial formula, then this would give us an independent

set in the graph of size equal to the number of clauses.

Which would contradict to the fact that there is

no such independent set in the resulting graph.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play