[Computational Complexity] Naming Complexity Classes
How do complexity classes get named? A proposal gets submitted to the Complexity Class Naming Commission (CCNC) which makes sure the class was not already named and the name has not been used before. The CCNC then puts out a Request for Comments to the community. Once the community responds, sometimes giving other suggestions for the name, the CCNC makes a formal recommendation to the Complexity Governing Council. The Council takes a final vote on the name.
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.
Posted by Lance to Computational Complexity at 7/11/2006 01:25:00 AM