re:battutaccia pessima!!!

Vai alla freccia - Homepage - BlogRoom - Mappa
Visualizza Messaggi.

Nick: AngryKat
Oggetto: re:battutaccia pessima!!!
Data: 19/9/2004 0.33.34
Visite: 35

mmm...

5.3 Cook's Theorem
The NP-complete problems are the hardest problems in NP, in the sense that if Q0 is any decision
problem in NP and Q is an NP-complete problem, then every instance of Q0 is polynomially reducible to an
instance of Q. As we have already remarked, the surprising thing is that there is an NP-complete problem
at all, since it is not immediately clear why any single problem should hold the key to the polynomial time
solvability of every problem in the class NP. But there is one. As soon as we see why there is one, then we'll
be able to see more easily why there are hundreds of them, including many computational questions about
discrete structures such as graphs, networks and games and about optimization problems, about algebraic
structures, formal logic, and so forth.
Here is the satis¯ability problem, the ¯rst problem that was proved to be NP-complete, by Stephen Cook
in 1971.
We begin with a list of (Boolean) variables x1; : : : ; xn. A literal is either one of the variables xi or the
negation of one of the variables, as ¹xi. There are 2n possible literals.
A clause is a set of literals.
The rules of the game are these. We assign the value `True' (T) or `False' (F), to each one of the
variables. Having done that, each one of the literals inherits a truth value, namely a literal xi has the same
truth or falsity as the corresponding variable xi, and a literal ¹xi has the opposite truth value from that of
the variable xi.
Finally each of the clauses also inherits a truth value from this process, and it is determined as follows.
A clause has the value `T' if and only if at least one of the literals in that clause has the value `T,' and
otherwise it has the value `F.'
Hence starting with an assignment of truth values to the variables, some true and some false, we end
up with a determination of the truth values of each of the clauses, some true and some false.
De¯nition. A set of clauses is satis¯able if there exists an assignment of truth values to the variables that
makes all of the clauses true.
Think of the word `or' as being between each of the literals in a clause, and the word `and' as being
between the clauses.
The satis¯ability problem (SAT). Given a set of clauses. Does there exist a set of truth values (=T or
F), one for each variable, such that every clause contains at least one literal whose value is T (i.e., such that
every clause is satis¯ed)?
Example: Consider the set x1; x2; x3 of variables. From these we might manufacture the following list of
four clauses:
fx1; ¹x2g; fx1; x3g; fx2; ¹x3g; f¹x1; x3g:
If we choose the truth values (T;T;F) for the variables, respectively, then the four clauses would
acquire the truth values (T; T; T;F), and so this would not be a satisfying truth assignment for the set
of clauses. There are only eight possible ways to assign truth values to three variables, and after a little
more experimentation we might ¯nd out that these clauses would in fact be satis¯ed if we were to make the
assignments (T; T; T) (how can we recognize a set of clauses that is satis¯ed by assigning to every variable
the value `T' ?).
The example already leaves one with the feeling that SAT might be a tough computational problem,
because there are 2n possible sets of truth values that we might have to explore if we were to do an exhaustive
search.
It is quite clear, however, that this problem belongs to NP. Indeed, it is a decision problem. Furthermore
we can easily assign a certi¯cate to every set of clauses for which the answer to SAT is `Yes, the clauses are satisfable.' The certi¯cate contains a set of truth values, one for each variable, that satisfy all of the
clauses. A Turing machine that receives the set of clauses, suitably encoded, as input, along with the above
certi¯cate, would have to verify only that if the truth values are assigned to the variables as shown on the
certi¯cate then indeed every clause does contain at least one literal of value `T.' That veri¯cation is certainly
a polynomial time computation