Talk:P-complete
From Wikipedia, the free encyclopedia
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)
-
- 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)
- 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)
