tag:blogger.com,1999:blog-3722233.post115259923098055740..comments2023-01-30T06:53:58.825-06:00Comments on Computational Complexity: Naming Complexity ClassesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-1153152333342303192006-07-17T11:05:00.000-05:002006-07-17T11:05:00.000-05:00Someone asked me how to get their class into the C...<I>Someone asked me how to get their class into the Complexity Zoo. You can submit a proposal to the CCNC or just realize the Zoo is now a wiki and edit it yourself. </I><BR/><BR/>After the wiki has been down for a while,<A HREF="http://www.scottaaronson.com/blog/2006/07/two-john-related-announcements.html" REL="nofollow"> Scott has re-taken control</A>. It is back up at <A HREF="http://www.complexityzoo.com/" REL="nofollow">http://www.complexityzoo.com/</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152791873678928412006-07-13T06:57:00.000-05:002006-07-13T06:57:00.000-05:00I...want to learn about and teach a few of the mos...<EM>I...want to learn about and teach a few of the most important classes beyond NP. Which ones should I choose? Besides the complexity zoo, is there somewhere I can get such information?</EM><BR/><BR/>A good place to look is various on-line course lecture notes. There are others, but good starting points include: <A HREF="http://www.wisdom.weizmann.ac.il/~oded/cc99.html" REL="nofollow">Goldreich's notes</A>, <A HREF="http://www.cs.berkeley.edu/~luca/notes" REL="nofollow">Trevisan's notes</A>, and, if I can plug my own, <A HREF="http://www.cs.umd.edu/~jkatz/complexity" REL="nofollow">Katz's notes</A>. (Note: I am not a complexity theorist, but I think this has the effect of making my notes somewhat easier to understand)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152738879430765432006-07-12T16:14:00.000-05:002006-07-12T16:14:00.000-05:00I am not a complexity theorist, but want to learn ...I am not a complexity theorist, but want to learn about and teach a few of the most important classes beyond NP. Which ones should I choose? Besides the complexity zoo, is there somewhere I can get such information?Prasenjit Mitrahttps://www.blogger.com/profile/03101031052830003793noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152736430587490182006-07-12T15:33:00.000-05:002006-07-12T15:33:00.000-05:00Why is IP not IPP? Don't "polynomial" and "protoco...Why is IP not IPP? Don't "polynomial" and "protocols" deserve a P each?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152730211797102322006-07-12T13:50:00.000-05:002006-07-12T13:50:00.000-05:00Watch out anonymous 2, #NP is a different class!Al...Watch out anonymous 2, #NP is a different class!<BR/><BR/>Also, since most complexity classes are defined using nondeterministic machines in some way nowadays, marking it in the name is not that informative.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152692730124672202006-07-12T03:25:00.000-05:002006-07-12T03:25:00.000-05:00This is an old one: "computer science is all about...This is an old one: "computer science is all about 0's and 1's. The famous P = NP question is no exception: P = NP iff either P = 0 or N = 1."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152683604219428052006-07-12T00:53:00.000-05:002006-07-12T00:53:00.000-05:00That would mean NP is P, which is false as we all ...That would mean NP is P, which is false as we all know...Cheshire Cathttps://www.blogger.com/profile/07463645065346922684noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152679675825683622006-07-11T23:47:00.000-05:002006-07-11T23:47:00.000-05:00Are you telling me NP is not Not P?Are you telling me NP is not Not P?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152664477964256012006-07-11T19:34:00.000-05:002006-07-11T19:34:00.000-05:00I feel BPP and BQP are quite well named. Why don't...I feel BPP and BQP are quite well named. Why don't we have a formal nomenclature system just like in Organic Chemistry. Will be fun though to remember all the classes then.<BR/><BR/><I> It's the class of problems that have at least a hope of being solved in polynomial time, since their proofs are polynomially verifiable.</I><BR/><BR/>Alas!!!! 1 million rests on poly time verifiability.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152663875563245092006-07-11T19:24:00.000-05:002006-07-11T19:24:00.000-05:00The name "NP" is positively inspired compared to "...The name "NP" is positively inspired compared to "NC". Don't get me wrong, Nick is a stand up fellow, but if questions like P =? NP and P =? NC are fundamental to computer science, the N's should probably have something in common.EERachttps://www.blogger.com/profile/08077133590614809086noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152647988822907392006-07-11T14:59:00.000-05:002006-07-11T14:59:00.000-05:00Karp's 1972 paper defines NP in terms of polynomia...<I>Karp's 1972 paper defines NP in terms of polynomial time verifiability.</I><BR/><BR/>I think this is what makes NP a natural class to separate from P. It's the class of problems that have at least a hope of being solved in polynomial time, since their proofs are polynomially verifiable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152647605960654222006-07-11T14:53:00.000-05:002006-07-11T14:53:00.000-05:00Karp's 1972 paper defines NP in terms of polynomia...Karp's 1972 paper defines NP in terms of polynomial time verifiability.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152631606387333022006-07-11T10:26:00.000-05:002006-07-11T10:26:00.000-05:00When NP was introduced nobody gave so much attenti...When NP was introduced nobody gave so much attention to its polynomial time verifiability. At that time non-determinism must have been a fancy word. I shouldn't coment much on the thread because the class NP is older than my age. I agree on PP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152631542530977982006-07-11T10:25:00.000-05:002006-07-11T10:25:00.000-05:00When NP was introduced nobody must have given so m...When NP was introduced nobody must have given so much attention to its polynomial time verifiability. At that time non-determinism must have been a fancy word. I shouldn't coment much on the thread because the class NP is older than my age. I agree on PP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152630330342329822006-07-11T10:05:00.000-05:002006-07-11T10:05:00.000-05:00Another example for a bad name is #P. We count the...Another example for a bad name is #P. We count the number of accepting paths of a NP machine, thus #NP would be much more appropriate. (Just like SAT is deciding if there is a truth assignment, and #SAT is counting such assignments.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1152624296325017362006-07-11T08:24:00.000-05:002006-07-11T08:24:00.000-05:00If one reads the original papers for hundred year ...If one reads the original papers for hundred year old results in math, one can see that it is not uncommon for the notation and even the definitions themselves to have been refined over the years. <BR/><BR/>I do not think the field is in need of a major rewrite, but by the same token I do think we shouldn't be afraid to do some house keeping, as suggested in Lance's previous post.<BR/>E.g. I've been arguing for a long time that we should downplay non-determinism in the initial definition of NP, and focus more on either the polynomial verifiability or the exponential-work/polynomial-time nature of finding a solution (exponentially many processors running for polynomial time).Anonymousnoreply@blogger.com