Template talk:ComplexityClasses

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)

New structure

I've been WP:BOLD and edited the template to make major changes in organization. I've made 3 groups of classes, those which are considered feasible (everything less powerful than what quantum computers can do in polynomial time), classes suspected to be infeasible (everything else which is not provably exponential time), and classes which are infeasible (exponential time classes and above).

We also need to establish some criteria for inclusion, or else this template will soon get flooded with every single class on the Complexity Zoo. For instance I feel 2-EXPTIME is a fairly non-notable class, and shouldn't be included. But I haven't removed/added any classes. --Robin (talk) 03:15, 26 August 2009 (UTC)

By your explanation, BQP should be in the "suspected to be infeasible" column, shouldn't it?--Roentgenium111 (talk) 23:33, 15 November 2010 (UTC)

I'm not quite sure how I feel about this organisation - it seems to split up the classes fairly evenly, but I'm not sure if it's the most "interesting" or objective way of dividing them up. In complexity theory references they often clearly distinguish between classes "within P" and classes "harder than P" but I'm not sure if this is the most useful way either. It's probably okay for now but suggestions would be welcome. Dcoetzee 00:41, 16 November 2010 (UTC)