Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Naming Complexity Classes

Expand Messages
  • Lance
    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
    Message 1 of 1 , Jul 10, 2006
    • 0 Attachment
      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.
      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.

      --
      Posted by Lance to Computational Complexity at 7/11/2006 01:25:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.