The Turing omnibus : 61 excursions in computer science by Dewdney A. K

Author:Dewdney, A. K [Dewdney, A. K]
Language: eng
Format: epub
Tags: Electronic data processing, Computers, Informatica, Toepassingen, Informatique, Ordinateur, Informatik, Computer systems
Publisher: Rockville, MD : Computer Science Press
Published: 1989-03-07T05:00:00+00:00

THE TURING OMNIBUS

(Xi + X3 + X4){xi + X2 + X4)(x2 + a:3)(ji:, + X2 + X4)

(X3 + X4){X2 + X3) X2 = 0 /^ \v X. = 1

(X2 + X4){X2 + X3)(X2 + X4) X2 = 0 ^^ ^\ X. = 1

(Xj + X4) (X3 + X4)(X}) (X4) (X4)(X3)

X^ = 0/ \ X3 = 1 X3 == 0 / \x3 =1 X3 = 0/ \ X3 = 1 X3 = 0 / \ X3 = 1

(X4)(0) (X4)

(0) 0 (0) 0(0) 0 (0) 0 0 (0)

Figure 105 The tree implicit in the Davis-Putnam algorithm

212

algorithm mentioned earlier. The reason for this lies in the Davis-Putnam algorithm's ability to prune unsuccessful branches from its search tree.

There is no algorithm known at present that is guaranteed to solve an n-variable satisfiability problem in less than exponential time. Specifically, there is no algorithm which is guaranteed to solve it in polynomial time (see Chapter 14), say in time proportional to n^'oi less for some fixed power k. Is this inability to find an efficient algorithm for the satisfiability problem due to our own relative stupidity, or is it just possible that no such algorithm exists?

To make matters worse, there is a much simpler version of this problem which seems to be equally difficult: Find an efl&cient (say, polynomial-time) algorithm which, for each product-of-sums expression, merely outputs a 1 if the expression is satisfiable and a 0 if it is not. This is called the satisfiability decision problem (or, sometimes, just the satisfiability problem ^\\^n the context is clear). No satisfying assignment is asked for, just a decision about whether the expression is satisfiable.

To see why the satisfiability problem is central (and difl&cult), it is necessary to examine product-of-sums expressions in a new light. Rather than view them as logical expressions which are either true or false depending on how their variables are assigned, we may regard such formulas as a kind of language in which a great many mathematical ideas may be expressed. For example, consider this well-known problem in graph theory: Given a graph 6", color its vertices red, yellow, and blue in such a way that if any two vertices are joined by an edge, then the vertices receive different colors.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.