Cardinality of strings … 2

Some NP-complete problems, indicating the redu...
Image via Wikipedia

I have to make a confession. When I wrote the post below I was genuinely puzzled by the issue and what seemed to be a mistake in P, NP, and NP-Completeness, but just as I was about to press “publish” I saw that several pages earlier Professor Goldreich had stated:

“We consider finite objects, each represented by a finite binary sequence called a string.”

Although 15 pages later writes of “the set of all strings” I am now assuming he means in the sense he first used…

But I did not have the heart to not post my message as I worked on it for a little bit.

%d bloggers like this: