tag:blogger.com,1999:blog-3722233.post2657149028088071297..comments2022-12-04T13:54:21.319-06:00Comments on Computational Complexity: How important is the PROOF of Cooks theorem for my ugrad class?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-3722233.post-57661536151426913562012-04-27T14:57:11.208-05:002012-04-27T14:57:11.208-05:00@DaveMB
Thanks, that is indeed easy!@DaveMB<br />Thanks, that is indeed easy!Kevinhttps://www.blogger.com/profile/13315715886823365629noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21449664799356864492012-04-23T15:05:34.503-05:002012-04-23T15:05:34.503-05:00I also think giving a few reductions from NP-compl...I also think giving a few reductions from NP-complete problems to SAT before proving the NP-completeness of SAT is helpful in understanding why the proof works.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17445953745609847142012-04-23T14:49:06.835-05:002012-04-23T14:49:06.835-05:00another alternative: write a first order formula s...another alternative: write a first order formula stating that c is an accepting computation of NTM M on x, and show them how to translate this into a polynomial size propositional formula.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61396554871743954972012-04-23T10:01:13.481-05:002012-04-23T10:01:13.481-05:00Proving that "there exists an NP-complete pro...Proving that "there exists an NP-complete problem" is much easier than Cook-Levin. Define A_{NP}, by analogy with Sipser's other notation, to be {(M, w, 1^t): M is an NDTM and it is possible for M to accept w within time t}. Then you can reduce an arbitrary NP problem to A_{NP} quite easily. This makes even more sense if you proved that A_{TM} is complete for the TR languages under <=_m reductions back in the computability section.<br /><br />You can then phrase Cook-Levin as constructing a reduction from A_{NP} to CNF-SAT or to CIRCUIT-SAT, changing hardly anything. This makes SAT a little less magical -- it's not the "original NP-complete problem", it's just historically the first interesting one, as @CSProf says above.DaveMBhttps://www.blogger.com/profile/00779581893863396042noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50973282406065488162012-04-23T09:27:42.842-05:002012-04-23T09:27:42.842-05:00Bill, this is a question that I also pondered each...Bill, this is a question that I also pondered each and every time I taught Cook's theorem. I like the circuit-SAT approach; and then there's another that I have been using, which is to use a TILING PROBLEM as my basic NPC example. Mapping Tm computations to tilings is, in my opinion, more transparent than the classic reduction to SAT. It is even a bit of a game. Basically, you just write down the computation history by laying cards on a table according to simple rules.<br /><br />Having done that, I reduce tiling to SAT, which is again quite easy and a more typical use of SAT (that is, an example of a pattern that they can use for many other problems).<br /><br />When I take this route, I tell them that Cook reduced to SAT directly, just for historical interest.<br /><br />An advantage of the approach via tiling is that the tiling problem is "generic" in a sense: with very minor modifications, the problem becomes complete for other classes involving space and time (e.g., PSPACE, EXP). There are a lot of nice things you can do with it.Amir ben-Amramhttp://www2.mta.ac.il/~amirben/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32378052334168488462012-04-21T01:36:41.054-05:002012-04-21T01:36:41.054-05:00I never taught this material so perhaps my opinion...I never taught this material so perhaps my opinion should carry less weight, but I would split the proof into two parts to be taught in two different parts of the course. When you introduce the concept of Turing machines, before nondeterminism is even in the picture, you show the equivalence of Turing machines and circuits (maybe just in one direction to avoid discussing uniformity). This can be done in the more general context of equivalence between computational models (like multi-tape TMs, unrestricted grammars, programs in C, lambda calculus etc.). I remember being pretty amazed when I first saw that all of these models are actually equivalent (hardware design and software design is actually the same thing, who would have guessed). You don't need to prove all of the equivalences, just prove for circuits and tell them about the rest without proof and maybe give an easy example in the homework. Then, when you get to NP completeness, you state Cook-Levin, and now the proof becomes very simple because we already know that TMs can be translated into circuits, so we just need to show that CIRCUIT-SAT is NPC.<br /><br />I think this approach gives the students sufficient time to "digest" the first part, so by the time you get to the second part, they are already convinced that TMs can be converted to circuits. Therefore they can dedicate all of their mental effort to the second part.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18673925635715916992012-04-20T16:32:52.701-05:002012-04-20T16:32:52.701-05:00I am assuming that in the computability part of yo...I am assuming that in the computability part of your course you introduce<br />universal Turing machines (students can read the rhetoric in Turing's paper, which is GREAT) and complete c.e. sets.<br /><br />Since you define NP by bounded existential quantification, it is then a simple observation that<br /><br />Thm1 There are NP-complete languages<br /><br />Then the polynomial hierarchy and complete languages for the sigma_i, pi_i levels are good homework questions.<br /><br />Now one definitely should state <br /><br />Thm2 There are interesting NP-hard languages<br /><br />together with a list.<br /><br />I believe the easiest proof of Thm2 is via the Circuit SAT route, after showing how circuits can simulate Turing machines.<br /><br />The question is how detailed you want these proofs to be, and this depends on the character of the course, and the mathematical abilities of the students. For smart enough students, too much detail is counterproductive. Do you want students to believe the proof or to be able to reproduce it?CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53758604841058444562012-04-20T12:57:06.911-05:002012-04-20T12:57:06.911-05:00I also think that giving a proof of Cook's th...I also think that giving a proof of Cook's theorem (or its extended sketch) is important. (Just like to give a proof-sketch of Goedel's theorem in a logic course.) This shows WHY we can forget all this "mess" (states, transitions, cell contents, etc.) and land in a 0-1 realm of CNFs. This will pay off: students will then trust in CNFs and circuits. And will better understand why, say, Clique problem is "the same" as SAT. From my experience, the only small technicality, which sometimes confuses students, and which should be explained in details is that the event "if A and B then C" in a TM is equivalent to the event "not A or not B or C is true". Then they understand that instructions of TM are, in fact, clauses. After that we can take a vocation, and say "good bye TM".Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62080356431704848912012-04-20T06:06:32.109-05:002012-04-20T06:06:32.109-05:00I also cover the Garey-Johnson proof in CMSC651 an...I also cover the Garey-Johnson proof in CMSC651 and I really like doing the proof. It may be mechanical but its so clever and shows why SAT is such a basic problem.samirhttps://www.blogger.com/profile/12398855828681012949noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66872597337494649782012-04-20T03:25:03.715-05:002012-04-20T03:25:03.715-05:00I have great fun teaching the standard (Garey-John...I have great fun teaching the standard (Garey-Johnson) proof, one of the highlights of my intro theory class. Be excited about it and the class will find it exciting too.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64659123068580843862012-04-20T02:55:10.743-05:002012-04-20T02:55:10.743-05:00I teach a very similar course in Florence and, so ...I teach a very similar course in Florence and, so far, I have always taught the proof of the Cook-Levin's theorem. As far as I can see, the students do not have so many problems in understanding the proof, even because they have already seen something very similar while proving that Turing machines are equivalent to unrestricted grammars or (if I have time) while proving the undecidability of the Post correspondence problem. In other words, when I teach the C-L theorem, the students already know that the computation of a Turing machine can be emulated by different formalism (if powerful enough) and they are not surprised to see that this can be done by using logical formulas: that's why the proof requires no more than half an hour and, as far as I can see during the oral examination, it is understood by the majority of my students.Piluhttps://www.blogger.com/profile/03928357405404408731noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73567093221242552222012-04-19T22:56:06.797-05:002012-04-19T22:56:06.797-05:00The proof we use here at Waterloo follows a long s...The proof we use here at Waterloo follows a long sequence of concepts from systems and programming languages that students are already rather familiar with:<br /><br />1) Introduce non-determinism as a parallel search on a very large size cluster (I actually never use the word non-determinism, since it is rather confusing at this early stage). <br /><br />2) Then introduce a very restricted subset of the C language enhanced with a "Try" statement as in "Try x=0 and x=1" to write such parallel programs. The Try statement causes a Unix fork of the code with parallel execution on two machines thereafter. <br /><br />3) At this time, we introduce the concept of NP problems as problems whose solution can be found in polynomial time on a (very large) cluster using a C+Try program.<br /><br />4) We then show some simple code samples illustrating (3) above such as a C+Try program solving TSP or SAT.<br /><br />5) We give the compiler rules to compile any arbitrary C+Try program into a SAT formula, which as a target architecture might be a bit unusual but no more than, say, java being compiled into pcode instead of machine code. This is about two slides worth of simple rules.<br /><br />6) Argue the correctness of the compilation rules, i.e. the program accepts/rejects if and only if the SAT formula is satisfiable.<br /><br />7) Point out that if instead of a JVM someone gave us a SAT-VM "executing" (i.e. solving) SAT formulas in polynomial time we have a means to solve any problem in NP.<br /><br />8) Hence SAT is NP-complete.<br /><br />I've tried several other ways of teaching this, and settled on this one over the years.<br /><br />The fact that students have already used fork, have a natural familiarity with exhaustive search, are familiar with large Google clusters and know about compilers that compile into weird target architectures means that they buy into the proof both at a technical level and at an intuitive "seems sound" kind of way.Alex Lopez-Ortiznoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78069556754898436982012-04-19T21:37:09.784-05:002012-04-19T21:37:09.784-05:00Primitive Recursion: I do it sometimes, not other ...Primitive Recursion: I do it sometimes, not other times.<br />AGREE that its certainly FAR LESS IMPORTANT than a PROOF of<br />Cook's Theorem.<br /><br />Arithmetic and Poly Hierarchy- These I LIKE. Arithmetic Hierarchy<br />gives you a way to classify sets beyond HALT. Poly hier analogous.<br />AGREE that there are less important than proof of Cook's theorem,<br />BUT these are easily understood by the students, which is a plus.<br /><br />ANYWAY, the comments have convinced me to TO the proof of Cooks theorem, using the CIRCUIT SAT proof.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80744301149308115102012-04-19T18:48:57.578-05:002012-04-19T18:48:57.578-05:00...Other things can be added like Primitive Recurs...<em>...Other things can be added like Primitive Recursive Functions, the arithmetic hierarchy, the polynomial hierarchy.</em><br /><br />Why would you even think of adding those topics to an undergrad class? If your choice is one of those topics or the proof of Cook's theorem, I would go with the latter.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61178918873108078232012-04-19T16:01:35.561-05:002012-04-19T16:01:35.561-05:00I concur with @DaveMB that it's crucial to pro...I concur with @DaveMB that it's crucial to prove that an NP-complete problem exists before you start doing reductions. Without that fact reduction proofs are circular logic, and an astute student may suspect that the class of NP-complete problems is actually empty, and that all the related theorems are vacuously true. (It sounds like that was sticking in @Thamas' craw.)<br /><br />It's true that only 5ish students follow the entire SAT proof, but I think most come away at least believing that NP-complete languages exist, which is something.<br /><br />I do wonder if there's an approachable nonconstructive proof that there exists an NP-complete problem, and if that would be a better compromise.<br /><br />I've had better results with the argument in the Goodrich-Tamassia algorithms book. You invoke Church-Turing to say that any TM can be compiled to machine code, and according to the computer architecture course every machine instruction can be built out of boolean circuits. Then you aggregate those into a humongous-yet-polynomial circuit for the entire computation. The setup is hand-wavy but it lets you talk in terms of core prerequisite CS concepts, instead of introducing SAT and working through all the technical details of the formula widgets.Kevinhttps://www.blogger.com/profile/13315715886823365629noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90876266211755484352012-04-19T15:14:10.851-05:002012-04-19T15:14:10.851-05:00I second the CIRCUIT-SAT approach (I typically fol...I second the CIRCUIT-SAT approach (I typically follow CLRS). I think at least an outline of the proof idea is helpful to students.Piotr Indykhttp://people.csail.mit.edu/indyk/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88085163145537358462012-04-19T14:15:05.967-05:002012-04-19T14:15:05.967-05:00I have used the VERIFY definition of NP
{ x | (ex...I have used the VERIFY definition of NP<br /> { x | (exists^p y) [ (x,y) \in B }<br />and then used Turing Machines.<br /><br />Based on your comments and others if I do it (likely given<br />the comments) I will do it using CIRCUIT-SAT.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11851635564576779302012-04-19T14:10:59.686-05:002012-04-19T14:10:59.686-05:00Actually the title of the course is ELEMENTARY THE...Actually the title of the course is ELEMENTARY THEORY OF COMPUTATION,<br />and the content is<br />Reg Langs (DFA,NFA,Reg Exp),<br />CFGs,<br />Decidable, undecidable stuff,<br />P, NP stuff.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6407034920554955302012-04-19T14:09:04.514-05:002012-04-19T14:09:04.514-05:00I am not sure how the proof you saw DIFFERS from t...I am not sure how the proof you saw DIFFERS from the `boring proof"<br />I ask nonrheoticallyGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15519165018009344522012-04-19T14:03:02.079-05:002012-04-19T14:03:02.079-05:00When I was a student, we just were just given the ...When I was a student, we just were just given the statement "SAT is NP-Complete" and moved on to reductions. This bugged me for a long time (but apparently not enough to look up the proof): where does the `first' NP-Complete problem come from? Some time later somebody SAID that you CAN code a computation into a formula, but not actually how. (Your point 8.) Then I was enlightened, as I could see that this was surely possible and the that details are for most purposes irrelevant.<br />I later came to view the proof of Cook's Theorem as reduction from NON-DETERMINISTIC TURING MACHINE ACCEPTANCE to SAT, where the former is trivially NP-Complete. I think that is an elegant way to view it.Thamashttps://www.blogger.com/profile/17766605868066955395noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65812354773324062812012-04-19T13:06:43.314-05:002012-04-19T13:06:43.314-05:00I (think) I prefer the proof of Cook's Theorem...I (think) I prefer the proof of Cook's Theorem via CIRCUIT-SAT - and then I would vote strongly for actually giving the proof, at least via pictures. Although it's not really different, the translation from NTMs to circuits seems to me like it would be more intuitive than the translation to formula, for someone who's never seen it before. I think this has something to do with the fact that circuits *compute* something, in essentially the same way a TM does, whereas formulas don't "compute" anything, per se.<br /><br />I think the idea that there is a universal NP language because the computation history of a Turing machine can be encoded into a circuit/formula is a very important one. In my (granted, limited) experience when you just *tell* students "here's some big idea" without showing them, they forget rather quickly. Of course, as you point out, even when you show them, they may not get it the first time. Also I agree strongly with your point 7.<br /><br />The CIRCUIT-SAT proof also has the advantage that it leads naturally to other useful ideas in complexity, like the fact that SUCCINCT CIRCUIT-SAT is NEXP-complete, the relationship between time on a TM and size of a circuit, and the Karp-Lipton Theorem.Joshnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30782181680458508192012-04-19T12:49:27.163-05:002012-04-19T12:49:27.163-05:00I first saw the normal boring proof of Cook’s Thm ...I first saw the normal boring proof of Cook’s Thm in such a class as yours. Then in a grad class the professor gave a proof sketch in 30 seconds. <br /><br />Just write a tableau of circuits to compute the ith tape character at time j (add extra character for encoding where the head is). This is clearly possible, just look at the i-1, i, i+1 positions of the previous time step. Now you have to write out the guts of the circuit using formulas. This is technical, but easily believable. The circuit computes a finite function, and a formula can do this just as well. Then you’re done. <br />Also, I think this proof delivers much more understanding than just writing everything out. I was pretty amazed when I saw this proof: is it really that easy? Can this professor say in 30 seconds what we spent 30+ minutes on before?<br /><br />Anyhow, that is my recommendation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91675361381230475002012-04-19T12:23:17.823-05:002012-04-19T12:23:17.823-05:00I'm very happy you covered the proof when I to...I'm very happy you covered the proof when I took the grad class. Before that, I thought the proof involved very complex ideas, and afterwards I saw it was mostly mechanical.<br /><br />When I teach Cook's theorem, I tell the students that there are theorems that are easy to conjecture, but hard to prove, and theorems that are hard to come up with, but then easy to prove. Cook's theorem is the latter if it is stated as: given a non-det poly time turing machine, there is a SAT instance of poly size that is satisfiable iff the machine says yes. I discuss how much more information I give when I say that than when I just say: NP-complete problems exist. Then I sketch some rules of the formula, and that's it. The rest is just mechanical and somewhat easy to believe, check online, or do yourself.Guilhermehttp://www.uniriotec.br/~fonsecanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86080639689156533142012-04-19T11:44:52.016-05:002012-04-19T11:44:52.016-05:00I'm sorry for your classes, but the Cook-Levin...I'm sorry for your classes, but the Cook-Levin Theorem is really false:<br /><br />This “theorem”, in fact, is not a genuine theorem, for its proofs are incorrect, since into them is used the hidden non-proved (faulty, really) assumption (or hidden axiom, contradictory with ZFC), that states that a polynomial p(n) that upper bounds the running time of some NTM that decides in nondeterministic polynomial time the problem to be reduced into that reduction to the SAT can be always anyway provided (either that p(n) is known a priori or can be computed by a poly-time DTM). This is not always accurate.<br /><br />See the complete proof at http://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdfAndré Luiz Barbosahttp://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdfnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29831574226977081232012-04-19T11:40:47.015-05:002012-04-19T11:40:47.015-05:00In the automata course, there were already analysi...In the automata course, there were already analysis of the behavior of simpler kinds of automata. So a description of the Turing machine made sense, and Cook's Theorem made sense. In more advanced CS courses, you skim over the details of the Turing machine, so Cook's Theorem is more complicated to explain.<br /><br />So, from the perspective of someone who will take more advanced courses, it is best to include Cook's Theorem in automata theory.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.com