tag:blogger.com,1999:blog-3722233.post5378409382663154601..comments2023-01-30T06:53:58.825-06:00Comments on Computational Complexity: How I Find Homework ProblemsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-19456328838414118762010-07-24T13:22:55.311-05:002010-07-24T13:22:55.311-05:00Consider the function f(phi)=1 if phi is SAT and f...Consider the function f(phi)=1 if phi is SAT and f(phi)=0 if phi is not in SAT. If P=NP f is computable in poly-time and reduces SAT to A. So A is NP-complete by definition. The assumption is that every NP-complete set is also P-complete so A must be P-complete too.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82725427217794691002010-07-23T17:59:56.517-05:002010-07-23T17:59:56.517-05:00Every language in NP poly-time reduces to A (since...<i>Every language in NP poly-time reduces to A (since P=NP) so A is NP-complete.</i><br /><br />that doesn't make any sense to meAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23866595047880995692010-07-23T17:17:06.042-05:002010-07-23T17:17:06.042-05:00A is now P-complete by assumption
why are you al...<i>A is now P-complete by assumption</i> <br /><br />why are you allowed to make this claim?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47425604827253950492010-07-21T10:51:40.483-05:002010-07-21T10:51:40.483-05:00As I am taking your computational complexity class...As I am taking your computational complexity class in the fall. I have written down the solution :)Tom Haydenhttps://www.blogger.com/profile/16677008700952361553noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49118938818837871972010-07-21T05:22:21.105-05:002010-07-21T05:22:21.105-05:00Here's the solution (SPOILER): Assume NP-compl...Here's the solution (SPOILER): Assume NP-complete = P-complete. SAT is now P-complete and thus in P so P=NP. Let A = {1}. Every language in NP poly-time reduces to A (since P=NP) so A is NP-complete. A is now P-complete by assumption so every language in P log-space reduces to A. Since A, like every finite language, is in log space we have L=P=NP. <br /><br />The other direction: If NP=L then every language A in NP (except Sigma^* and the empty set) is both NP-complete and P-complete so these are the same classes.<br /><br />This comment will be removed when I actually do give this problem for homework.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82076868142712993092010-07-20T07:19:32.447-05:002010-07-20T07:19:32.447-05:00Are you going to post the answer? =)Are you going to post the answer? =)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33533464917875438212010-07-17T17:35:27.987-05:002010-07-17T17:35:27.987-05:00that is great source of ideas, reallythat is great source of ideas, reallyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54720567293396668322010-07-17T16:44:14.078-05:002010-07-17T16:44:14.078-05:00L = LOGSPACE.
The problem is a little more tricky...L = <a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:L#l" rel="nofollow">LOGSPACE</a>.<br /><br />The problem is a little more tricky than just composing logspace computations.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5285096811299037762010-07-17T16:31:27.894-05:002010-07-17T16:31:27.894-05:00what is L?what is L?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36827296003061814992010-07-17T14:55:23.295-05:002010-07-17T14:55:23.295-05:00isn't that just another way of saying "sh...isn't that just another way of saying "show that for two computations that are in L, their composition is in L "?carter t schonwaldhttps://www.blogger.com/profile/16546056304179288828noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58387313067593352302010-07-17T00:55:22.213-05:002010-07-17T00:55:22.213-05:00A New Kind of Grammars: A new kind of generative g...A New Kind of Grammars: A new kind of generative grammars that can produce the empty language is designed in this book.<br /><br />http://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687Milind "Milz" Bandekarhttp://www.amazon.com/New-Kind-Grammars-generative-grammars/dp/1452828687noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33008643728536584832010-07-16T15:11:24.125-05:002010-07-16T15:11:24.125-05:00A pretty one: both directions require discovering ...A pretty one: both directions require discovering something instructive (at least in my solution).Cescnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64267513044185174012010-07-16T11:00:32.679-05:002010-07-16T11:00:32.679-05:00Right.Right.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73473195396873043122010-07-16T10:20:12.944-05:002010-07-16T10:20:12.944-05:00Where NP-completeness is w.r.t. polytime reduction...Where NP-completeness is w.r.t. polytime reductions and P-completeness is w.r.t. logspace reductions?Anonymousnoreply@blogger.com