Problem Detail: I know that the complexity class $mathsf{P}$ has complete problems w.r.t. $mathsf{NC}$ and $mathsf{L}$ reductions. Are these two classes the only possible classes of reductions under which $mathsf{P}$ has complete problems? Also, what classes of reduction can be used for $mathsf{NP}$ beside polynomial-time reductions?
Asked By : user2346
Answered By : Tsuyoshi Ito
Your questions contain a few incorrect or unclear phrases. Neither “complexity class X has Y reduction” nor “we can use Y reduction for complexity class X” makes sense. In addition, there are at least two definitions known under the name “polynomial-time reductions,” both of which are used to study NP-completeness: polynomial-time many-one reductions and polynomial-time Turing reductions. But in this answer, I will ignore the difference between many-one reductions and Turing reductions, and I will focus only on the resource restrictions of reductions, because otherwise the answer will become too long and unfocused. Now I will restate what you might want to ask, and answer them. Are there any definitions of reductions with respect to which NP-completeness can be defined, other than polynomial-time reductions? Are there any definitions of reductions with respect to which P-completeness can be defined, other than NC reductions and log-space reductions? As Artem and Raphael said, you can define whatever you like. Are there any definitions of reductions actually used to study NP-completeness in the literature, other than polynomial-time reductions? Are there any definitions of reductions actually used to study P-completeness in the literature, other than NC reductions and log-space reductions? Yes. For example, Papadimitriou uses log-space reductions throughout his textbook [Pap94], including the definition of NP-completeness. (Note: in [Pap94], the term “L-reduction” means something completely different from log-space reduction.) As for P-completeness, NCk reductions are mentioned in [GHMRSS00]. This is a special case of NC reductions, and more general than log-space reductions for k≥2. But are they really different notions, or just different definitions for the same notion? Currently, no one knows. For example, log-space reducibility and polynomial-time reducibility are equivalent if and only if L=P. [GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi, and Takayoshi Shoudai. The Parallel Computation Project: Volumes I–III, 2000. http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/ [Pap94] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2222
