Template talk:Complexity classes

Computing Template‑class

	This template is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
Template	This template does not require a rating on Wikipedia's content assessment scale.

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)[reply]

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)[reply]

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)[reply]

New structure[edit]

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)[reply]

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

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)[reply]

"Important" complexity classes[edit]

Is limiting to "important" complexity classes a good idea? I suspect, with proper formatting, we could fit all of List of complexity classes in the navbox comfortably. BenKuykendall (talk) 17:40, 18 February 2019 (UTC)[reply]

In that list's current state, sure. But the complexity zoo has zillions of classes that are unlikely to ever get a full Wikipedia article, but reasonably could appear in List of complexity classes. So restricting to "important complexity classes" (construed broadly) strikes me as good future-proofing here. Bernanke's Crossbow (talk) 20:32, 6 May 2022 (UTC)[reply]