Timeline for definition of NP [closed]
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 25, 2013 at 12:06 | comment | added | Bruno | @Mark, are the first two chapters of some (and actually almost any) standard textbook on the subject "a lot of stuff"? Yet I agree with the second part of your comment concerning Wikipedia's article: The first paragraphs of the introduction are not enough. But if you click on "4 Equivalence of definitions" in the Contents, you'll have an acceptable proof, and even a reference to some standard textbook (Sipser's). In other words, if you just read Section 2.1.2 in Arora and Barak's textbook, you won't have a complete proof, but as soon as you look at the definitions, you have everything! | |
| Mar 25, 2013 at 11:59 | comment | added | user30035 | [@Mark Sapir: A "Wiki" is quite a general thing, and not the same thing as "Wikipedia", which is a very special kind of wiki with lots more properties. I've seen Wikipedia editors in the past imploring people not to abbreviate Wikipedia to [the already taken term] "Wiki"] | |
| Mar 25, 2013 at 11:22 | comment | added | user6976 | @Bruno: But that was exactly the point of the question. Isn't it? It is not easy to find a good explanation and it requires reading a lot of stuff. The comment of Steven Landsburg that it is enough to read the first and second paragraphs of a Wiki article is wrong: you need to read the first and second chapters of some recent book (one of infinitely many). | |
| Mar 25, 2013 at 10:16 | comment | added | Bruno | Mark, you should'nt skip Chapter 1! There, it is clearly and formally defined what a machine is, and what it means for a machine to "run another one". | |
| Mar 24, 2013 at 22:45 | comment | added | user6976 | Looked at Section 2.1.2 of Arora and Barak. The explanation there is not precise enough (at least not to my taste). For example, what does it mean "then the machine will run another machine"? How a TM can run another TM? It is not a critique of the book. The target readers probably would "eat" that explanation without a problem. The problem starts when you try to apply it in an algebraic setting (say when you try to simulate the machine in a group). Then you actually need a much more precise definition of the machine. | |
| Mar 24, 2013 at 22:30 | comment | added | Henry Cohn | I agree that some texts don't explain this well or even at all, but some of the best ones do (for example, see Section 2.1.5 in Goldreich or Section 2.1.2 in Arora and Barak). | |
| Mar 24, 2013 at 22:20 | history | closed |
Benjamin Steinberg Steven Landsburg Steve Huntsman Misha Henry Cohn |
off topic | |
| Mar 24, 2013 at 21:48 | comment | added | user6976 | In defense of the question. It is indeed a basic and easy fact, but I do not know a CS text where it is fully explained. For example, the text in Wiki uses a word "guess" which is a valid CS slang but for a non-CS person, it is not clear how a Turing machine can "guess" anything. | |
| Mar 24, 2013 at 21:22 | comment | added | Noah Schweber | In general, questions like this are a better fit for mathstackexchange. | |
| Mar 24, 2013 at 21:18 | answer | added | user6976 | timeline score: 3 | |
| Mar 24, 2013 at 21:09 | comment | added | Steven Landsburg | Did you get as far as the second paragraph of the Wikipedia article on NP? | |
| Mar 24, 2013 at 20:58 | history | asked | Dale | CC BY-SA 3.0 |