tag:blogger.com,1999:blog-3722233.post2895608456630484768..comments2024-11-11T13:10:42.993-06:00Comments on Computational Complexity: Question and Metaquestion about Students emailing you problemsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-16783028865992106252007-09-16T19:10:00.000-05:002007-09-16T19:10:00.000-05:00Anonymous 10: Think about it a little harder.Anonymous 10: Think about it a little harder.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75958258348817925352007-09-16T18:48:00.000-05:002007-09-16T18:48:00.000-05:00Given what is known it is immediate that every MAX...<I>Given what is known it is immediate that every MAXSNP-hard problem (under L-reductions) is also APX-hard (under AP-reductions).</I><BR/><BR/>This seems tricky, at least in trying to use a crude analogy I have got stuck. (Assume we care only about maximization problems). Since <BR/> MAX SNP subset APX<BR/>it seems that every APX hard problem should be MAX SNP hard, not vice-versa. The analogy is that<BR/> P subset EXP<BR/>and every EXP hard problem is P hard...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33374014755065026512007-09-15T19:07:00.000-05:002007-09-15T19:07:00.000-05:00For those asking for a BB for computer theory, you...For those asking for a BB for computer theory, you can check out the Usenet newsgroup <A HREF="http://groups.google.com/group/comp.theory/topics" REL="nofollow">comp.theory</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82526646211181178272007-09-15T10:54:00.000-05:002007-09-15T10:54:00.000-05:00Given what is known it is immediate that every MAX...Given what is known it is immediate that every MAXSNP-hard problem (under L-reductions) is also APX-hard (under AP-reductions). However, simce MAXSNP is a proper subset of APX (because of the min/max issue) and likely a proper subset of the APX maximization problems (though we don't know this for sure since both might be contained in FP), the MAXSNP-complete problems are a proper subset of the APX-complete problems and likely of the APX-complete maximization problems. Moreover, even within MAXSNP it is quite possible that this also holds since the AP-reductions are more liberal than L-reductions. This last question seems the only one where we don't have a natural answer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16270010386506630342007-09-15T09:13:00.000-05:002007-09-15T09:13:00.000-05:00Pardon my mistake... since MAX SNP is a subset of ...Pardon my mistake... since MAX SNP is a subset of APX the answer to a) is partially determinedAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48393417794932346102007-09-14T17:57:00.000-05:002007-09-14T17:57:00.000-05:00Thanks for the comments. The max vs min issue I di...Thanks for the comments. The max vs min issue I did not realize before, but it does not seem central, and I still don't really have the answers I really wanted:<BR/><BR/>a) are the statements "FOO is an APX maximization problem" and "FOO is a MAX-SNP maximization problem" related (does one imply the other?)<BR/><BR/>b) same, !@$#$ -> !@$#$-hard<BR/><BR/>c) same, !@$#$ -> !@$#$-complete<BR/><BR/>Thanks,<BR/>AnonymousAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75255755351626985882007-09-14T07:08:00.000-05:002007-09-14T07:08:00.000-05:00All problems in MAX-SNP can be constant-factor app...All problems in MAX-SNP can be constant-factor approximated. But MAX-SNP contains, by definition, only maximization problems. Thus, APX strictly contains MAX-SNP.<BR/><BR/>However, other problems, like minimization problem, can be "placed" in MAX-SNP via reduction to a MAX-SNP problem. The closure of MAX-SNP under L-reductions (introduced by Papadimitriou and Yannakakis when they defined MAX-SNP) is exactly APX-PB, which is the class of all polynomially bounded problems in APX.<BR/><BR/>If we use PTAS-reductions instead of L-reductions, then APX is equal to the closure of MAX-SNP.<BR/><BR/>(See Khanna et al., On syntactic versus computational views of approximability, SIAM J. Comput. 28, 1998.)BMhttps://www.blogger.com/profile/15006817456252127173noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2825145705912120272007-09-13T22:06:00.000-05:002007-09-13T22:06:00.000-05:00Hey Bill, I thought you might like this given your...Hey Bill, <BR/><BR/>I thought you might like this given your like of Dylan parodies.<BR/><BR/>http://www.youtube.com/watch?v=Nej4xJe4TdgAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67305888562493964142007-09-13T19:15:00.000-05:002007-09-13T19:15:00.000-05:00Would it be a good idea to set up a bulletin board...Would it be a good idea to set up a bulletin board (is there already one?) for Complexity (and in general, Theoretical CS) related questions? From personal experience, a google search while trying to solve a computer <I>technology</I> related question (say on programming, installing and using stuff, system administration, and so on), is very likely to turn up the answer, if it exists, on a bulletin board somewhere. Perhaps a theory-related BB would be a good resource to have.<BR/><BR/>I have in fact been thinking about setting one up for some time now, but was not sure about whether it would help or be a nuisance -- the homework issue,spam/flame, etc -- to the theory community.<BR/><BR/>(Basically your blog is currently the main source of computational complexity vox populi to my brain, so it seemed natural ...)<BR/><BR/>PhilipAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46035542889000124572007-09-13T16:28:00.000-05:002007-09-13T16:28:00.000-05:00The problem MAX3SAT is MAX-SNP-complete via L-redu...The problem MAX3SAT is MAX-SNP-complete via L-reductions, and APX-complete via AP-reductions.<BR/><BR/>http://books.google.com/books?id=_C8Ly1ya4cgC&pg=PA22&lpg=PA22&dq=max+snp+apx&source=web&ots=mGa6hQZVnz&sig=Cpugt4sQ-t-xNDC4OZl9Wi8hstQ#PPA22,M1Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76743150331158768162007-09-13T13:54:00.000-05:002007-09-13T13:54:00.000-05:00This is a legit question, probably coming from an ...This is a legit question, probably coming from an undergrad (or starting PhD student) starting to read about inapproximability.Anonymousnoreply@blogger.com