Talk:P-complete

I'm confused by the following paragraph from the article:

Lempel-Ziv (1978 paradigm) Data Compression - given strings s and t, will compressing s with an LZ78 method (such as Unisys's LZW technology) add t to the dictionary? (Note that for LZ77 compression such as gzip, this is much easier, as the problem reduces to "Is s in t?".)

I don't know the details of LZ77 or LZ78, but I don't understand the second sentence above. First, it seems that it must mean "Is t in s"; it can't be that compressing a string adds all superstrings to the dictionary. However, even in this revised form, it seems unlikely. s has (in general) about n^2 substrings. Surely they aren't all added to the dictionary?

-- Cwitty

The most basic P-complete problem is this: given a Turing machine, an input for that machine, and a number T (written in unary), does that machine halt on that input within the first T steps? It is clear that this problem is P-complete: if we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so is every other problem in P.

I don't pretend to understand the subtle nuances here, but is it certain that the final word should be "P-complete" rather than "P"? I mean, if any #P problem is in NC, then so is every other problem (since they can be reduced to each other). Even if this is correct, it could be a little clearer. - JustinWick 03:47, 18 November 2005 (UTC)

I'm not sure I understand. We're talking about P here, not #P. It does say "P", not "P-complete" at the end, and this is correct. The class P-complete is defined under logarithmic-space transformations, so there isn't necessarily such a transform between any two problems in P. Can you explain a little more what you mean? Thanks. Deco 02:57, 19 November 2005 (UTC)

Firstly I meant to write "P" instead of "#P" (I had too many articles open at once, must have gotten confused). Secondly someone was helping me with this comment and I think they got confused, and what I meant to say was - why is it "P" at the end rather than "P-complete". Thanks! - JustinWick 17:20, 19 November 2005 (UTC)

Sorry for getting confused about the errors. The argument is completely analogous to why P=NP provided that there is a polynomial-time algorithm for an NP-complete problem. A problem is P-complete if there is an NC-reduction from any problem in P to that problem, by definition. Consequently, if there is an NC algorithm for a P-complete problem, there is an NC algorithm for every problem in P: first use the NC reduction to the P-complete problem, then solve that using its NC algorithm. Deco 00:14, 20 November 2005 (UTC)

Wow, that explaination actually made sense. It also seems so obvious now, thanks! I wonder, is this too "obvious" to put in the article, or can it be clarified somehow? Thanks again! - JustinWick 00:32, 20 November 2005 (UTC)

Why the emphasis on parallel computers?

Why do we launch into parallel computing in the intro paragraph? I don't think this is how P is usually described. Can we stick with Turing machines in the intro, and bring up parallel computers later? --Doradus 11:07, 15 August 2007 (UTC)

Because while P is primarily important for determinstic settings, P-complete is primarily important for distinguishing problems that are either believed to required more than logarithmic space (under the assumption L ≠ P) or be difficult to parallelize (under the assumption that NC ≠ P). Dcoetzee 23:22, 28 August 2007 (UTC)

Yes, but this over-focus on the *motivation* makes it very difficult to read this article. Even as a professor in computer science, I had a hard time extracting from this article *what the definition and properties of a P-completene problem are*. Instead there is a lot of messy talk about how it relates to parallelisation. That may be important for the motivation and interpretation, but not for the technical definitions. All talk about parallelisability should be gathered into its own paragraph, e.g. titled "Applications to Parallelisability", so that it doesn't muddle the waters unnecessarily. As it stands, this article does not communicate the subject matter well.

L reductions?

The Complexity Zoo site at Caltech requires L reductions to qualify for P-completeness. I've never heard this before; I thought P reductions were sufficient. Unfortunately the Zoo doesn't cite its sources; does anyone know if the Zoo is right on this one? --Doradus 11:13, 15 August 2007 (UTC)

Once again, under P reductions all problems in P are P-complete, which is useless. This applies generally: all problems in any complexity class C are C-complete under C reductions. It's entirely typical to use log-space many-one (L) reductions and I've never seen anyone use anything else. You may be thinking of NP-completeness. Dcoetzee 08:07, 16 August 2007 (UTC)

I'm sure I'm confusing it with NP-completeness. That just leaves the question: why does our article say that "polylogarithmic" reductions are required? (And isn't the set of "polylogarithmic" reductions exactly the same as the set of polynomial reductions anyway?) --Doradus 22:49, 28 August 2007 (UTC)

Some definitions use L reductions and others use NC reductions. The idea is that if a problem is P-complete under L reductions and L ≠ P, then the problem is not in L (and so requires more than log space). Similarly, if a problem is P-complete under NC reductions and NC ≠ P, then the problem is not in NC (and so difficult to parallelize). I think it's worthwhile to explain all this in simpler terms and I'll do so now. Dcoetzee 23:22, 28 August 2007 (UTC)

Why do we still say "polylogarithmic" in several places? Isn't "polynomial" sufficient, and simpler? For instance, O(n²log n) is a subset of O(n³). --Doradus 16:08, 30 August 2007 (UTC)

"Polylogarithmic" means polynomial in log n, which is something different from what you're assuming. Dcoetzee 22:15, 31 August 2007 (UTC)

Oh. Well, then we definitely need some kind of definition of "polylogarithmic" on this page, be it a link or a simple inline definition. But I'm skeptical; O(logⁿ) is a subset of O(n), so wouldn't polylogarithmic time fall within linear time? --Doradus 17:36, 1 September 2007 (UTC)

Yes. The reduction is restricted to operate in at most polylogarithmic time on polynomially many processors. I'm not sure what your misunderstanding is, but it's not like it has polynomial time to work in. Every problem in P can be solved in polynomial time, we're interested in a hard subset of these. A definition would be good. Dcoetzee 08:27, 2 September 2007 (UTC)

Ok, thanks for your patience.  :-) --Doradus 23:13, 5 September 2007 (UTC)

Add More Problems

See article: "A Compendium of Problems Complete for P" by Raymond Greenlaw , H. James Hoover , Walter L. Ruzzo

Link to article: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644

Consider Adding Link

XP-complete is a class of parameterized problems. They are related to P-complete problems because their slices are infinitely often P-complete.

It could be good to link to the XP section of the Parameterized complexity article.