[Solved]: Are there complete problems for P and NP under other kinds of reductions?

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, NC^k 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