Discrete Mathematics for Computer Science

310 CHAPTER 5 Analysis of Algorithms

and a truth assignment I to its variables-typically, here, one lists the true literals, such as

a, -b, c, --d, e, and-f.

Returns: Truth value I (4).

Solution. See Exercise 5 in Section 5.4, where a proof is sketched for 4) in conjunctive

normal form (CNF). (A proof for more general formulas 40 would involve a digression into

"parsing": Given a formula, how can we construct its parse tree?) 0

When people formally measure the complexity of such algorithms, they are likely to

use variant definitions of complexity, as in variants 1 and 2 in the next section.

In Section 2.5.6, we noted that it is generally assumed-but not proved-that no fast

algorithm exists that, given a propositional formula 4), can decide whether 4) is satisfiable.

This latter problem is called the propositional satisfiability problem, which is sometimes

referred to simply as SAT.

What we meant in Section 2.5.6 by "fast" was "polynomial time." It is commonly

assumed that there is no polynomial-time algorithm to settle propositional satisfiability.

However, nobody can prove it! This is often considered to be the most significant open

problem in theoretical computer science-and one of the most significant open problems

in all of mathematics.

Propositional satisfiability is the problem of the paradigm nondeterministic polyno-

mial time (A/P). We use satisfiability to motivate an almost-precise definition of A!'r.

We do not give the most common definition, which is in terms of something called "non-

deterministic algorithms." The definition we give, however, would be equivalent if that one

small bit of precision were added.

A problem is said to be in .M'P, or nondeterministic polynomial time, if there is a

polynomial time verifier algorithm V for the problem. In other words, V is an algorithm

that takes any input or and a purported proof that the answer for a should be TRUE and, in

polynomial time, verifies that the proof is correct. (Such an algorithm is sometimes called

a "guess-and-check algorithm": First, it guesses C, and then it checks the result. Here, C

stands for certificate.) The set of all A/'7 problems is called, simply, A/'r.

Note that in the definition of AFP, it makes no difference whether there are any, or

many, k-ary relations C where A(ar, C) = FALSE. It matters only whether there exists one

C for which A(a, C) = TRUE.

An example of a nondeterministic polynomial time problem is to determine if a CNF

for which each term consists of exactly three literals is satisfiable. The problem can be

solved for a given interpretation for each of the literals by examining each of the n clauses

in some fixed order and determining whether each clause is TRUE or FALSE in this inter-

pretation. The CNF is satisfiable if each of its clauses is TRUE in the given interpretation.

The reader can devise a polynomial time algorithm for determining whether a clause with

three literals is TRUE or FALSE in a given interpretation. After repeating this process at

most n times, once for each clause, the answer will be found in polynomial time.

The definition above is not the traditional definition of the term nondeterministic poly-

nomial problem, but it is equivalent.

Every decision problem in 'P is also, trivially, in AF'P. (Why?) The famous P .AFT'

conjecture is the statement that this is true-that is, that not every problem in A/'7 is also

in P.