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.

###### Related Articles

- Levels of Infinity (xamuel.com)

Advertisements