Talk:Complexity class

Sublinear time classes

I'm surprised there aren't pages for linear time, log(n) time, or even constant time. They're not as intriguing as P vs. NP, but many important (albeit ordinary) tasks require knowing about the distinctions between these complexity classes, eg. when to use linked lists vs. arrays or vectors.

Any thoughts?

These are only really useful in the analysis of algorithms with regard to particular machine models; for example, most sorting algorithms assume that you have random access, that the input has a particular structure, and that a comparison or exchange is a unit operation. In complexity theory, we try to avoid any such assumptions by using classes that are invariant over a large class of abstract machines, like P, NP, and L.

For example, anything you can do on a random access machine in polynomial time, you can also do on a Turing machine (with or without multiple tapes) in polynomial time. If the input is a graph, you can specify it in adjacency matrix form, adjacency list form, or incidence matrix form - in these coarse classes, it doesn't matter. You can't say that about the classes you mention. In fact, a Turing machine can't do much of anything useful in log time, although a random access machine can.

This might be (should be?) discussed somewhere in the encyclopedia. Deco 22:36, 28 Apr 2005 (UTC)

#P and #P-complete

Can someone please put Sharp-P and Sharp-P complete in the correct locations on this graph? Or are they omitted for a reason? (I would do this if I were confident enough that I could figure out precisely where they go! Complexity Zoo indicates it's at least as hard as NP) Actually there seems to be a lot of complexity classes missing that are considered "important" at the bottom of each article. What is the criterion for inclusion in this chart? - JustinWick 03:32, 18 November 2005 (UTC)

Strictly speaking, they wouldn't really belong in this diagram (besides, its inaccurate and not very useful). This is because #P (and other counting classes) are functional classes defined for Turing machines that output the value of a function f:{0,1}^* -> Z rather than making a yes/no decision. On the other hand, you can make connections by considering the decision analogs of counting problems: that is, define a language that contains (x,i,b) where b is the i-th bit of the function f(x) for an input x to the original counting function. Anyway, to answer your question, #P is contained in PSPACE (as is the entire counting hierarchy, a possibly infinite hierarchy of #P counting classes). Its exact relation to NP is unknown, but the best result is Toda's Theorem: the whole of the polynomial hierarchy (and so NP) is contain in P^#P (a polynomial time machine with oracle access to a #P language). Moreover, P^PP = P^#P (binary search) and NP is in PP by definition, but its not clear that NP is in #P. —Preceding unsigned comment added by 75.88.67.113 (talk • contribs)

Relationship between BPP, BQP and NP

In the Table it seems that BQP$\subseteq$NP. However in the BQP article it is stated that BPP$\subseteq$BQP. In the BPP (complexity) article it is stated that it is an open question whether NP contains BPP. So who is wrong? Chithanh 14:55, 30 March 2006 (UTC)

It shoud be that BPP $\subseteq$BQP. No other inclusions are known between the classes BPP,BQP and NP. —Preceding unsigned comment added by 130.235.35.227 (talk) 08:38, 18 October 2007 (UTC)

This diagram is inaccurate.

Uh, who the hell made this not very useful and inaccurate inclusion chart?

-PSPACE-complete is a proper subset of PSPACE since L is in PSPACE and you can separate them by direct diagonalization.

-It is not known if BQP is contained in NP, at this point they are incomparable. The best upper bound known is PP (or AWPP), see L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Computing 26:1524-1540, 1997. and L. Fortnow and J. D. Rogers. Complexity limitations on quantum computation, Proceedings of IEEE Complexity'98, pp. 202-209, 1998.

-Its not known if NC is properly contained in PSPACE

-Its not known that LogCFL (context-free languages) are a proper subset of NC (only that they are in NL).

This entire diagram should just be deleted. —Preceding unsigned comment added by 75.88.67.113 (talk • contribs)

I find this chart rather useful even if it's slightly inaccurate (instead of eliminating the table how about fixing it?). A few responses to your points:

• I can more or less see how PSPACE-c would be a proper subset of PSPACE. However, I still do not understand enough of your argument to see why this is. No mention is made about it in the PSPACE-complete article or in TQBF. A Proof or reference would help a lot. (Similarly, wouldn't NP-complete be a proper subset of NP? From the PSPACE-c article, it is implied that NP-complete is a proper subset of PSPACE-complete. But proof would be needed for this as well. Co-NP complete is missing, but I guess it is insignificant enough to ignore.)

• Response: The proof is as simple as I outlined. By direct diagonalization we have that L is a proper subset of PSPACE. If PSPACE=PSPACE-c then every language in PSPACE is complete (under log-space many-one reductions) and in particular, any L-complete language is complete for PSPACE. Now you can simply reduce, say QBF to an L-complete language, solve it in L and we have that PSPACE = L, a contradiction. Its not mentioned because its trivial. Moreover, complexity theorists do not find these results interesting since completeness depends on the type of reductions used. Its certainly thought that NP is a proper subset of PSPACE, but that is not known.

• You are right, the BQP article confirms that the relationships between BQP and NP is unknown. I have modified the diagram accordingly.
• The statement "Its not known if NC is properly contained in PSPACE" doesn't make adequate sense. It is not known if NC=P, but NC is analogous to problems solved through parallel computation, which can be simulated using a Turing Machine (or an Alternating Turing machine where AP=PSPACE), thus seems to be within the realm of PSPACE (problems deemed solvable by deterministic or non-deterministic Turing machines).

• Response: How can it not make adequate sense? Its a simple statement. It is not known whether the infinite union of all log^k(n) bounded depth circuits is properly contained in PSPACE. Alternating polynomial time is a different model whose relationship to (uniform) circuits is unknown. The containment is not known to be proper, period.

• According to NC (complexity), $NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}$, and since context free is in NL, then context free is a proper subset of $NC_{2}$. So in some (somewhat inaccurate) sense, the diagram is correct.

• Response: I don't think you understand what a proper subset is. None of these containments is known to be proper (the only such proper containment is for low complexity classes is $AC_{0}\subsetneq NC_{1}$). You're reaching for straws here, the diagram is in some "inaccurate" sense correct? Its inaccurate period.

--Stux 18:11, 26 December 2006 (UTC)

Also, templates would help make the diagram easier to manipulate. If it's not too much trouble I will see if I can make some. Then again, with a correct diagram, many changes would be unnecessary. --Stux 18:26, 26 December 2006 (UTC)

Shouldn't there be a dashed line between P and NP-Complete? 128.32.192.6

It should be noted that P ≠ EXPTIME, as there are EXP problems that are known not to be in P (e.g. winning strategy in the GO game) 128.139.226.37 (talk) 20:47, 22 June 2008 (UTC)

Whether PSPACE-complete is a proper subspace of PSPACE depends on the type of reduction used. If polynomial-time reductions are used, it's possible that PSPACE=PSPACE-complete, because we don't know whether P=PSPACE. If log-space reductions are used, then the subset is proper. I typically see polynomial-time reductions used in the definition of PSPACE, and the choice of reduction may even result in different sets. Since all this can't be indicated in a diagram, I suggest simply sticking to a dotted line connection.

It is true that BQP and NP are incomparable.

It's true that NC is not known to be properly contained in PSPACE. The largest space known to be properly contained in PSPACE is still L.

I don't know whether LogCFL is known to be a proper subset of NC, but I doubt it - usually only circuit classes have proper subset relationships with classes inside P. Dcoetzee 21:29, 22 June 2008 (UTC)

Variability of ease-of-reading across complexity class articles

Reading P, NP, P-complete, etc, I see that there's a lot of variation in how easy the articles are to read for someone with little math knowledge. Would it be possible for all articles to have a very gentle paragraph to introduce simplistic examples, or perhaps for a single very-gentle introduction covering complexity classes to be created? For this target audience (ie, people like me) it's often a good idea to show why problems are (or aren't) hard. Thus, for factorisation it's useful to give an example of two big prime numbers, (and maybe mention where numbers this big are used, perhaps in some common web crypto?) and their product, and then say that "If you can do x calculations per second it'll take you y seconds to solve this problem". The subset sum problem is used as an example, yet the subset sum problem page doesn't have clear, easy, beginner's level examples to explain it. Dan Beale 13:23, 31 July 2007 (UTC)

Agreed, this fails to explain the topic from the ground up. 1Z (talk) 10:30, 11 September 2015 (UTC)

Here's one for you

Hey, so according to your chart NP is a subset of P. But over here P=NP it looks as though the opposite is true. What gives?Solsticefan (talk) 04:58, 28 April 2009 (UTC)

Huh? I think you're reading the chart backwards. Ben Standeven (talk) 05:50, 24 December 2009 (UTC)

Correct (AFAIK) relations between "important" classes

If someone with better editing skills than me wishes to correct and extend the diagram of classes, here's a list of class relationships. (As noted above, the contents of the "-Complete" classes depend on which reduction you use, and they aren't normally considered complexity classes in any case.)

• DLOGTIME (aka NC_0, I believe) is a proper subset of AC_0 (aka ALOGTIME with constant alternations). The latter class contains the language of strings consisting entirely of 1s, but the former does not.
• AC_0 is a proper subset of L, since L contains PARITY and AC_0 does not.
• $L=SL\subseteq RL\subseteq NL\subseteq LOGCFL\subseteq NC$
• RL and LOGDCFL are subsets of SC. I don't know if NL is, or if SC is contained in NC.
• The context-free languages by themselves ("Type 2" in the table) are a proper subset of LOGCFL; the classic example of a non-context-free language is $\{a^{n}b^{n}c^{n}\}$, which is clearly in L. Prima facie there may be deterministic context-free languages not in L, and nondeterministic ones not in LOGDCFL or NL.
• The regular languages are a subset of NC_1 (hence of L) and of the context-free languages. They are not a subset of AC_0, since PARITY is a regular language. The classic example of a non-regular language is $\{a^{n}b^{n}\}$, which is both context-free and in L.

• All the classes above are subsets of P, and $P\subseteq ZPP\subseteq RP\subseteq BPP\subseteq BQP$; AFAIK it is unknown whether BQP properly contains L.
• Of the "infeasible classes", $P\subseteq UP\subseteq NP\subseteq AM\subseteq PH\subseteq P^{PP}\subseteq IP=PSPACE$.
• $BQP\subseteq PP$ (according to a comment above), $BPP\subseteq AM$, and $RP\subseteq NP$. Otherwise, I do not believe that there are any known relations between the classes between P and PSPACE. [co-NP is somewhere between ZPP and PH.]
• NC and SC are properly contained in PSPACE. AFAIK, PP may be equal to L.
• #P is essentially the function class associated with P^{PP}, as I understand it.
• "Type 1", the context-sensitive languages, is equal to NLINSPACE, while its deterministic analog is equal to LINSPACE. It is unknown whether they are equal. Both classes are properly contained in PSPACE, and properly contain SC and the context-free languages. They cannot equal any of the other classes above, because they are not closed under polynomially-increasing reductions. Note that some deterministic context-sensitive languages are PSPACE-complete.

• P is properly contained in EXPTIME (which is properly contained in 2-EXPTIME), NP in NEXPTIME, and PSPACE in EXPSPACE. But it may be that EXPSPACE = EXPTIME, that NEXPTIME = BPP, or that EXPTIME = ZPP. (Not at once, of course.)

• $2-EXPTIME\subset ELEMENTARY\subset PR\subset R\subset RE\subset ALL$. R is labeled "Decidable" in the current graph, RE is labeled "Type 0 (recursively enumerable)", and ALL is labeled "Decision problem". "Undecidable" is simply the complement of R.

Ben Standeven (talk)

I usually work with classes bigger than P, so I can't say much about the smaller classes. BQP is not known to properly contain L, since even PP is not known to properly contain L. I don't think AM or PH are known to be in PP. They are in P^PP by Toda's theorem. --Robin (talk) 13:55, 24 December 2009 (UTC)

Yeah, that's the result I was thinking of; I've changed the claim above.

Now that I think about it, it looks like $NC_{i}$ is contained in $SC_{i}$, by a depth-first search algorithm. This will only take polynomial time, since there are only polynomially many nodes in the circuit. So $NC\subseteq SC$. Ben Standeven (talk) 21:48, 4 January 2010 (UTC)

No, that doesn't work, because the circuit may have fanout greater than one, so that the nodes get visited more than once each. Ben Standeven (talk) 05:43, 8 January 2010 (UTC)

Error in Reduction section

The following statement is in error: "being able to reduce another problem, Π1, to a known NP-complete problem, Π2, would indicate that there is no known polynomial-time solution for Π1". Reducing a problem Π1 to an NP-complete problem only tells you that Π1 is at worst NP. It says nothing about how easy Π1 is. I'm not sure what the author originally had in mind: perhaps "being able to reduce a known NP-complete problem, Π2, to another problem, Π1, would indicate that there is no known polynomial-time solution for Π1"?

Ross Fraser (talk) 23:33, 12 April 2010 (UTC)

Names of classes

Are they correctly written in BOLDFACE? Or in normal ROMAN uppercase? I can guess myself only that they may not be written AS HERE. Incnis Mrsi (talk) 15:20, 27 May 2013 (UTC)

P/poly described incorrectly

In "Important complexity classes", the article states "P/Poly is the set of languages decidable by polynomial-circuit families. This should be the set of languages recognizable by polynomial-circuit families. As it stands, further in that first paragraph, the article states that P is a proper subset of P/Poly because "there are undecidable problems that are in P/Poly". --WowThisIsAnnoying (talk) 22:30, 25 August 2020 (UTC)

@WowThisIsAnnoying: The provided definition for P/Poly is correct, to my understanding. The textbook Computational Complexity by Sanjeev Arora and Boaz Barak, used heavily for this page, defines P/Poly as "the class of languages that are decidable by polynomial-sized circuit families" (pg. 108). After a quick google search I also see that these lecture notes for a course on advanced complexity theory at the University of Texas likewise define P/poly as "the class of languages decided by polynomial size circuits".

As for the "because there are undecidable problems that are in P/Poly", the lecture notes describe how there do exist undecidable languages in P/Poly. It gives the example that any unary language is in P/Poly ("since there is only one string per input length, if an input is in the language we may assign it a circuit which always outputs 1 and otherwise assign a circuit which always outputs 0"). But, as it points out, "the class of unary languages includes undecidable languages!" Perhaps I am missing something here, but this seems to corroborate what the page says. Still, I have gone ahead and changed the wording from "because there are..." to "(for example, there are undecidable languages in P/Poly)".

-- Jaydavidmartin (talk) 22:03, 13 October 2020 (UTC)

Hierarchy Theorems

Is there a reason why we give weaker statements for the Space- and Time Hierarchy Theorems here? The usual definitions are given in the corresponding articles, using different factors. — Preceding unsigned comment added by Loudwaterzebra (talk • contribs) time, day month year (UTC)

There is no source given in this section, but only a reference to the theorem's main articles, where again this weaker definition is not stated. — Preceding unsigned comment added by Loudwaterzebra (talk • contribs) 13:24, 12 March 2021 (UTC)

@Loudwaterzebra: I will look into this. Jaydavidmartin (talk)