Talk:Complexity class

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as start-Class on the assessment scale
Mid rated as mid-importance on the assessment scale

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)

Contents

[edit] #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)

[edit] Relationship between BPP, BQP and NP

In the Table it seems that BQP\subseteqNP. However in the BQP article it is stated that BPP\subseteqBQP. In the BPP 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 \subseteqBQP. 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)

[edit] 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 NC2. 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

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