Talk:P (complexity)

PTIME

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

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 (talk • contribs) 11:11, 2 January 2009 (UTC)

Merge content from PSIZE

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

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.