patternModerate
Are there complete problems for P and NP under other kinds of reductions?
Viewed 0 times
areproblemsothercompleteunderreductionsforkindsandthere
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#2222, answer score: 10
Revisions (0)
No revisions yet.