Professor Warren Esty, one of the authors of our main textbook, has made available a list of solutions to some of the problems from Chapter 1. They are most of the odd numbered problems. Please let him (or me) know if you find errors or typos, or if you have suggestions for alternative solutions or different approaches.

## 187 – The resolution method

September 19, 2011This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.

We would like to have a mechanical procedure (algorithm) for checking whether a given set of formulas logically implies another, that is, given , whether

is a tautology (i.e., it is true under all truth-value assignments.)

This happens iff

So it suffices to have an algorithm to check the (un)satisfiability of a single propositional formula. The method of truth tables gives one such algorithm. We will now develop another method which is often (with various improvements) more efficient in practice.

It will be also an example of a *formal calculus*. By that we mean a set of rules for generating a sequence of strings in a language. Formal calculi usually start with a certain string or strings as given, and then allow the application of one or more “rules of production” to generate other strings.

A formula is in *conjunctive normal form* iff it has the form

where each has the form

and each is either a propositional variable, or its negation. So is in conjunctive normal form iff it is a conjunction of disjunctions of variables and negated variables. The common terminology is to call a propositional variable or its negation a *literal*.

Suppose is a propositional statement which we want to test for satisfiability. First we note (without proof) that although there is no known efficient algorithm for finding in cnf (conjunctive normal form) equivalent to , it is not hard to show that there is an efficient algorithm for finding in cnf such that:

is satisfiable iff is satisfiable.

(But, in general, has more variables than .)

So from now on we will only consider s in cnf, and the Resolution Method applies to such formulas only. Say

with literals. Since order and repetition in each conjunct (1):

are irrelevant, we can replace (1) by the set of literals

Such a set of literals is called a *clause*. It corresponds to the formula (1). So the formula above can be simply written as a set of clauses (again since the order of the conjunctions is irrelevant):

Satisfiability of means then simultaneous satisfiability of all of its clauses , i.e., finding a valuation which makes true for each , i.e., which for each makes some true.

Example 1

From now on we will deal only with a set of clauses . It is possible to consider also infinite sets , but we will not do that here.

Satisfying means (again) that there is a valuation which satisfies all , i.e. if , then for all there is so that it makes true.

Notice that if the set of clauses is associated as above to (in cnf) and to , then

By convention we also have the *empty clause* , which contains no literals. The empty clause is (by definition) unsatisfiable, since for a clause to be satisfied by a valuation, there has to be some literal in the clause which it makes true, but this is impossible for the empty clause, which has no literals. For a literal , let denote its “conjugate”, i.e. if and if

Definition 1Suppose now are three clauses. We say that is aresolventof if there is a such that , and

We allow here the case , i.e. .

## 187 – The P vs NP problem

September 19, 2011This note is based on lecture notes for the Caltech course Math 6c, prepared with A. Kechris and M. Shulman.

**1. Decision problems **

Consider a finite alphabet , and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).

We use the notation to indicate the set of all “words” from the alphabet . Here, a word is simply a finite sequence of symbols from . For example, if is the usual alphabet, then

would be a word.

We are also given a set of words, and we say that the words in are *valid*. ( may be infinite.)

In the *decision problem* associated to , we are given as **input** a word in this alphabet. As **output** we say yes or no, depending on whether the word is in or not (i.e., whether it is “valid”).

We are interested in whether there is an *algorithm* that allows us to decide the right answer.

## 414/514 – Metric spaces

September 19, 2011This is **homework 2**, due Monday September 26 at the beginning of lecture.

Let be a metric space.

- Show that if is defined by , then is also a metric on .
- Show that if is open in then it is open in , and viceversa.

Recall that is open iff it is a union of open balls. Use this to explain why it suffices to show that if is open in then for any there is an such that

,

and similarly, if is open in then for any there is a such that

.

In turn, explain why to show this it suffices to prove that for any and any there is a such that

and, similarly, for any there is a such that

.

Finally, prove this by showing that we can take (no matter what is) and similarly, find an appropriate that works for (again, independently of ).

- Illustrate the above in as accurately as possible.
- Suppose that a sequence converges to in and to in . Show that .
- Is it true that a sequence is Cauchy in iff it is Cauchy in ? (Give a proof or else exhibit a counterexample, with a proof that it is indeed a counterexample.)
- Show that any dense subset of has the same size as .