187 – The P vs NP problem

September 19, 2011

This 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 {A}, and “words” on that alphabet (the “alphabet” may consist of digits, of abstract symbols, of actual letters, etc).

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

\displaystyle awwweeeedddfDDkH

would be a word.

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

In the decision problem associated to {V}, we are given as input a word in this alphabet. As output we say yes or no, depending on whether the word is in {V} 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.

Read the rest of this entry »