SAT to 3-SAT

Loading...

Do curso por University of California San Diego

Advanced Algorithms and Complexity

291 classificações

University of California San Diego

Advanced Algorithms and Complexity

291 classificações

Curso 5 de 6 em 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.

Na lição

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

Conheça os instrutores

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

Our next reduction is from satisfiability problem to 3-satisfiability problem.

That is, from a general version of a problem to its special case.

To construct such a reduction, we need to design a polynomial time algorithm

that takes as input a formula in conjunctive normal form, that is,

a collection of clauses, and produces an equisatisfiable formula in 3-CNF,

that is, a formula in which each clause has at most three literals.

By saying equisatisfiable, we mean that the resulting formula

is satisfiable if and only if the initial formula is satisfiable.

Once again, if the initial formula is F and

the resulting formula is F prime, then by saying equisatisfiable,

we mean that F is satisfiable if and

only if F prime is satisfiable.

To construct such a reduction,

we need to somehow get rid of all long clauses in our formula.

By saying long, we mean clauses that contain more that three literals.

Right.

To do this, consider such a long clause and denote by l1 and l2 some two literals

of this clause and denote by A the rest of this clause.

So once again, l1 and

l2 are two literal of the clause C, which we consider at the moment.

And A is the set of all other literals.

Now we are going to do the following, introduce a new, fresh variable y and

replace the current clause C with the following two clauses.

So the first clause contains literals l1, l2, and

y, so it is a disjunction of l1, l2, and y.

The second clause contains a negation of y and

all the other literals which we denote by a set A, okay?

Then we first of all note an important property.

The clause, the first of the two new clauses has length 3.

So we are okay with it.

We are happy with it.

We do not need to get rid of it.

At the same time, this clause is shorter than the following one.

Exactly by one literal.

Right?

So we are going to repeat this procedure while there is at least one long clause.

And for sure, we will stop at some point, because at each step,

we reduce some long clause with a shorter one.

We now need to prove that the constructed transformation is correct,

that the constructed reduction is correct, and that it takes polynomial time.

Concerning time, consider the running time, it is clear because

at each iteration we'll replace a clause with a shorter one.

This means that the total number of iterations is bounded from above

by the total number of literals in all the clauses.

This is clearly polynomial in the length of an input formula.

To prove that the constructed reduction is correct, we're going to

show that the initial formula F with a long clause is satisfiable if and

only if the resulting formula where we replaced a long clause with a 3-clause and

a shorter clause is also satisfiable.

To do this, consider these two formulas.

So this is F.

It contains a long clause.

And this is F prime that results from F by replacing this long clause

with the following two clauses, l1, l2 and y,

where y Is a fresh variable and a clause not y or A.

I assume now that the formula F is satisfiable and

take a satisfying assignment.

We are now going to extend it so that it also satisfies the formula F prime.

Recall that the only difference between the sets of variables of formulas F and

F prime is the variable y.

So our goal is to set y so that the resulting assignment

satisfies all the clauses of the formula F prime.

First of all, all the remaining clauses of F prime are satisfied

by exactly the same assignment that satisfies the formula F,

so our goal is to set y so that both the first two clauses are satisfied.

I mean, both the first two clauses of the formula F prime.

Okay, so to set the variable y,

we just check whether the current satisfying assignment of the formula F

satisfies one of the literals l1 or l2 or not.

So if it satisfies these two literals, we set y to 0.

In this case, the first clause of the formula F prime

is satisfied by one of l1 or l2.

The second clause, on the other hand, is satisfied by the variable y,

right, because we've just assigned the value 0 to y.

On the other hand, if l1 and

l2 are falsified by the current satisfying assignment,

then at least one of the literals from the set I should be satisfied.

In this case, we just set the value of y to 1, right.

In this case, the first clause is satisfied by the value of y

while the second clause is satisfied by one of the literals from the set A.

Okay, for the reverse direction, note that if we have a satisfying

assignment that satisfies the formula F prime,

then we can just discard the value of the variable y from this assignment,

and then what we get is a satisfying assignment for the formula F.

Why is that?

Well, for a simple reason.

What we need to show is that this clause is satisfied in a formula F,

but it must be satisfied, because at least one of l1,

l2, and all the literals of A should be satisfied.

Assume for the sake of contradiction that in the current satisfying assignment for

F prime, l1 is set to 0, l2 is set to 0, and

all the literals from the set A are also set to 0.

Then there is just no possibility to satisfy these two clauses

because no matter how we assign the value to y either the first clause or

the second clause is going to be unsatisfied.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play