Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
Note that if complexity class $C$ has a complete problem under a class of reductions $A$, then the same problem will be complete for $C$ under and class of reductions containing $A$.
Typically completeness proofs go through with much weaker class of reductions than usually stated (e.g. under $\mathsf{AC^0}$ reductions). Any class of reductions containing $\mathsf{AC^0}$ would suffice and there are uncountable many such classes.
You may also want to check the following paper:
As Artem notes in his comment, the question is rather unmeaning as you can define whatever you like. Let me illustrate where things start to be "kind of silly".
Some notation: For two problems $P,Q$, write $P \leq_F Q$ for some class of functions $F$ if there is $f \in F$ such that $P(x) = Q(f(x))$ for all inputs $x$ (of $P$), that is if $P$ can be $F$-reduced to $Q$. Write $XC_F$ for the class of $X$-complete problems with respect to $F$, that is
$\qquad \displaystyle XC_F = \{P \in X \mid \forall Q \in X.\ Q \leq_F P \}$.
Denote furthermore with $T_X$ the set of (asymptotically optimal) runtime functions of algorithms that compute functions in some set $X$.
Now consider an arbitrary (complexity) class of problems $X$¹. If we restrict reduction space $F$ in terms of time complexity -- everything is possible here -- there are roughly two cases:
$T_F \supseteq \Omega(T_X)$² -- reductions are not faster than problem solvers.
In this case, $XC_F = X$ -- this is clearly not very interesting for complexity theory. Considering such $F$ may be useful in practice, especially if $T_F \subseteq \Theta(X)$; you can reduce all problems in $X$ to a handful of problems which you can solve very well. Linear programming and SAT are typical examples because of highly optimised LP- resp. SAT-solvers.
$T_F \subseteq o(X)$ -- reductions are faster than problem solvers
Here interesting things can happen, that is $XC_F \subset X$ or $XC_F \neq XC_{F'}$ for different reduction spaces. Whether these facts have interesting ramifications depends on the concrete choice of $X$ and $F$. Note that $XC_F = \emptyset$ might happen, which is in itself interesting enough.
Things definitely become rather uninteresting when you choose $F$ so "small" that $\leq_F$ is sparse, that is few reductions are possible. Think of $X=\mathsf{NP}$ and $F$ such that $T_F \subseteq o(n)$; reductions have to shrink input sizes significantly and cannot spend too much time on it, so $F$ is not very powerful.
Note, though, that even a restriction to $T_F \subseteq O(1)$ leaves meaningful relations; for instance, "Is $x$ an even integer?" can be reduced to "Is $x$'s first bit 0?" in $O(1)$ time and space. So it might be interesting to study even such weak reductions to find out which problems are close to which others in terms of reduction complexity; you definitely see such differences in classic $\mathsf{NPC} = \mathsf{NP}C_P$ reductions.
Technically, there is a third case, for example $T_F = P$ and $T_X = \Theta(n^3)$; in this case -- if $F$ is reasonably rich -- the comments on case one apply. Note also that the question which case $F$ falls into may be interesting in itself: "$\mathsf{P=NP}$?" is essentially asking whether $T_F=\Theta(X)$ (and even whether $F = \Theta(XC_F)$).
