Template talk:ComplexityClasses

From Wikipedia, the free encyclopedia

Perhaps we should order these classes as best we can? Perhaps from smallest to largest (as far as we know)? -- Pkirlin 04:54, 8 November 2005 (UTC)

Could these classes be better categorised in the template? Also, some seem more "relevant" (not sure how to define this...) than others. I would expect 90+% of clicks would go to P and NP. Remy B 09:30, 18 July 2007 (UTC)

I believe it should be lexicographically ordered within each category. This is enough for now seeing how few classes there are but possible categories for the future: Kind of problem class, i.e. decision problem, function problem, counting problem, parity, etc. (does not seem to work for the current collection). Computational model or just semantic/syntactic classes (too small categories for the first, the second looks random). If further division needed, type of resources. I'm not entirely sure how to handle classes covering multiple models, PCP for instance. Lexicographic: #P, #P-C, 2-EXPTIME, BPP, BQP, coNP, coRE, coRE-C, EXPSPACE, EXPTIME, IP, L, P, P-C, PCP, PH, PR, PSPACE, PSPACE-C, R, RP, RE, RE-C, NC, NEXPTIME, NL, NP, NP-C, NP-hard, UP, ZPP C. lorenz (talk) 13:41, 28 January 2008 (UTC)