Are there complete problems for P and NP under other kinds of reductions?

Question

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?

Answer 1

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.

Answer 2

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:

• Agrawal, M, Allender, E., Impagliazzo, R., Pitassi, T., and Rudich, S., "Reducing the Complexity of Reductions", Journal of Computational Complexity, 10, pp.117-138, 2001. Preliminary version in Proceedings of ACM STOC, 2001.

Answer 3

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)$).

---

1. In order to be a "proper" complexity class, it needs to be some sort of "downward closed" w.r.t. complexity.
2. $\circ(X)$ for a function class $X$ and $\circ$ a Landau symbol is the natural extension of the usual Landau symbols, i.e. $\circ(X) = \bigcup_{f \in X} \circ(f)$.