If only we were so organized. Complexity classes get their name usually from the authors who invent them or occasionally by a later paper if the first paper didn't name the class or gave it an unmemorable name. Too often researchers will give a temporary name so they can work with a class and then keep that name out of laziness. Maybe I've been guilty of this a few times myself.
I could write several posts on badly named complexity classes. For now let me mention two important ones.
- NP for Nondeterministic Polynomial Time. But "nondeterministic" is not very descriptive. Logically ∃P would be better or PV for Polynomially Verifiable.
- PP for Probabilistic Polynomial Time. Since the error is not bounded away from one-half, the class is not a useful characterization of probabilistic computation. A better name would be Majority-P or just MP. BPP would then get the proper name PP and BQP would be just QP.
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.
ReplyDeleteI 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.
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).
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.)
ReplyDeleteWhen 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.
ReplyDeleteWhen 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.
ReplyDeleteKarp's 1972 paper defines NP in terms of polynomial time verifiability.
ReplyDeleteKarp's 1972 paper defines NP in terms of polynomial time verifiability.
ReplyDeleteI 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.
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.
ReplyDeleteI 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.
ReplyDeleteIt's the class of problems that have at least a hope of being solved in polynomial time, since their proofs are polynomially verifiable.
Alas!!!! 1 million rests on poly time verifiability.
Are you telling me NP is not Not P?
ReplyDeleteThat would mean NP is P, which is false as we all know...
ReplyDeleteThis 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."
ReplyDeleteWatch out anonymous 2, #NP is a different class!
ReplyDeleteAlso, since most complexity classes are defined using nondeterministic machines in some way nowadays, marking it in the name is not that informative.
Why is IP not IPP? Don't "polynomial" and "protocols" deserve a P each?
ReplyDeleteI...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?
ReplyDeleteA good place to look is various on-line course lecture notes. There are others, but good starting points include: Goldreich's notes, Trevisan's notes, and, if I can plug my own, Katz's notes. (Note: I am not a complexity theorist, but I think this has the effect of making my notes somewhat easier to understand)
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.
ReplyDeleteAfter the wiki has been down for a while, Scott has re-taken control. It is back up at http://www.complexityzoo.com/.