Talk:List of complexity classes

Untitled

Any reason there is no P/Poly article?

There is. It's just not listed here. Good catch. Deco 20:17, 15 January 2006 (UTC)

The APX link on this page directs to a page on an energy company called APX, not one relating to complexity. I can't even find the actual article about the complexity class APX. Does it exist? Interestingly, the talk page on the APX company's article has comments about complexity, so perhaps the whole page was changed somehow? —Preceding unsigned comment added by 76.24.185.33 (talk) 14:44, 3 December 2007 (UTC)

Why NP-complete is the hardest problems in NP

>NP-complete The hardest or most expressive problems in NP
It should be most expressive, but why the hardest?

They are "hardest" in the sense that if you can solve an NP-complete problem in polynomial time, you can solve any problem in NP in polynomial time; and conversely, if there is any problem in NP that can't be solved in polynomial time, no NP-complete problem can be solved in polynomial time. Hence in an informal sense they require "the most time" to solve of any problem in NP. Dcoetzee 11:04, 29 October 2009 (UTC)

references ?

What is the point of asking references for a list ? Arthur MILCHIOR (talk) 19:13, 10 July 2010 (UTC)

Perhaps the editor who tagged this page wants references for complexity classes that don't have their own article? --Robin (talk) 01:40, 11 July 2010 (UTC)

Illustration?

This list is useful, but wouldn't it be appropriate to have an illustration, like a Venn diagram to illustrate the relations between the different complexity classes? Perhaps that could make it easier to grasp the bigger picture, to "piece them together". 81.233.196.43 (talk) 23:28, 29 July 2015 (UTC)

Alphabetical?

David Eppstein: You seem to be editing alot of these complexity articles; it seems like putting complexity classes into alphabetical order is not as useful as putting them into an order of complexity list. Complexity classes in complexity order would make more sense, can you try this to make the article here better? ErnestKrause (talk) 16:37, 5 February 2023 (UTC)

They cannot be linearly ordered by complexity. See e.g. doi:10.1007/BF01368782. —David Eppstein (talk) 18:50, 5 February 2023 (UTC)

David Eppstein: The other Wikipedia articles on complexity do make an issue of illustrating the classes as being partially or completely imbedded in one another like this:

${\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}$

Even though what you say about ambiguities and unsolved problems in complexity is often true, it seems like breaking the list up into 2-3 parts might allow for a useful set theory type of ordering of the complexity classes such as in the table above. For example, would it help to break up the current alphabetical list into 4 lists like (a) Deterministic complexity, (b) Non-deterministic complexity, (c) Probabilistic complexity, and (d) Quantum complexity. Would this be useful or do you have a better way to look at this material? ErnestKrause (talk) 21:45, 6 February 2023 (UTC)