Talk:P (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics 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.
Mathematics rating:
C Class
High Priority
 Field: Discrete mathematics

PTIME[edit]

PTIME redirects here, but is not explained in the article. (Unless it should be pointing to polynomial time?) -- Beland (talk) 07:30, 25 September 2008 (UTC)

PTIME is simply another name for P. Dcoetzee 05:31, 26 September 2008 (UTC)

A set diagram similar to the one and NP-complete would be helpful. Ccalvin (talk) 00:45, 21 November 2008 (UTC) That was actually at NP not NP-complete. NP-complete, P would all benefit from related diagrams. Ccalvin (talk) 00:49, 21 November 2008 (UTC)

DTIME[edit]

Why does the wiki page say that P is DTIME\left(n^{O\left(1\right)}\right)? Should it not be P = \bigcup_{k \in \mathbb{N}}DTIME\left(n^{k}\right)? —Preceding unsigned comment added by Kinkydarkbird (talkcontribs) 11:11, 2 January 2009 (UTC)

Merge content from PSIZE[edit]

It is unlikely that we have anything interesting to say about PSIZE other than the fact that its uniform version is P and its non-uniform version is P/poly. I don't think we need an article for PSIZE. --Robin (talk) 18:23, 20 August 2009 (UTC)

Alternative characterizations is WRONG[edit]

Immerman's and Vardi's theorem says that P is captured by FO + IFP only for ordered structures! It is a major open problem to find a logic capturing P in full generality (and many scientists think that this might not be possible at all, i.e. such a logic might not exist). — Preceding unsigned comment added by 89.71.116.216 (talk) 10:43, 28 May 2013 (UTC)

I added a caveat in the article, but whether the original statement is wrong depends on how you read it. Being a complexity class, P is a family of languages, which are sets of binary strings. In descriptive complexity, a binary string is represented by a structure with a linear order (or the successor relation, or something similar making the indices unambiguous), and a unary predicate for the individual bits. This is an ordered structure, so as a complexity class in the usual sense, P is indeed characterized by FO + IFP. Descriptive complexists also consider more general setting for complexity classes where one takes sets of structures in an arbitrary signature, closed under isomorphism, whose description is recognizable in the given class. It is in this setting that unordered structures happen, and FO + IFP is weaker than P.—Emil J. 12:35, 28 May 2013 (UTC)
I think it is really important to explicitly say "ordered structures". ESO captures NP in broader sense and to compare P and NP in terms of capturing logics, one needs a logic capturing P on all structures.