## 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.