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?

  • $\begingroup$ What does "X-complete has y-reduction" mean; that $L_1 \leq_y L_2$ for all X-complete $L_2$ and $L_1 \in X$? $\endgroup$ – Raphael Jun 4 '12 at 10:04
  • $\begingroup$ @Raphael I'd rather rephrase it as P has NC and L reduction and L reduction to P-complete. $\endgroup$ – user2346 Jun 4 '12 at 13:19
  • 3
    $\begingroup$ You can use whatever reductions you want. It depends on what you wish to define. These are all just definitions, a definition is good if it is natural and/or if it can be used to prove nice theorems. You could study $P$ with $P$ reductions, but that would be kind of silly. $\endgroup$ – Artem Kaznatcheev Jun 4 '12 at 15:54
  • 1
    $\begingroup$ @Raphael, I think your edit to the title has made it harder to understand. $\endgroup$ – Kaveh Jun 6 '12 at 23:53
  • $\begingroup$ @Kaveh: The former title was too generic and did not represent the question well. Feel free to propose another titel that suits the question. $\endgroup$ – Raphael Jun 7 '12 at 11:51

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:

  • 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.

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)$.
  • $\begingroup$ I am afraid that this answer is rather confusing in the sense that the only people who can “decipher” the notation in this answer are probably those who already know what is written here. In addition, it contains a few minor errors: (1) You have to require P∈X in the definition of XC_F to match the definition to the rest of the answer. (2) Because F is a class of reductions and X is a class of decision problems, it is sloppy at best to say “F⊇X,” “F⊂X,” or “F=X.” (3) It is sloppy at best to write F=o(n) or F=O(1). $\endgroup$ – Tsuyoshi Ito Jun 5 '12 at 20:56
  • $\begingroup$ I had hoped the notation would serve purely as readable shorthands; there certainly is nothing deep here. (1) Very true, changed. (2) Also true, but harder to fix. I added an explanatory note. (3) Oh dear, doubly meaningless! Edited. Thanks for the remarks! $\endgroup$ – Raphael Jun 6 '12 at 9:17
  • $\begingroup$ Footnote 2 is still problematic. For example, the class of functions f such that given strings x and y, whether f(x)=y or not can be decided in time polynomial in |x| is not necessarily equal to the class of polynomial-time many-one reductions! This is because in the former, an algorithm only has to check whether a given y is the correct value of f(x) instead of computing f(x) from scratch. The former class contains the latter, but the inclusion is strict unless P=UP∩coUP. $\endgroup$ – Tsuyoshi Ito Jun 6 '12 at 14:07
  • $\begingroup$ @TsuyoshiIto: Hm. I see that the footnote is counterproductive. What I really want to say is that the functions in F are faster/slower than those in X -- so I should just say that, shouldn't I? $\endgroup$ – Raphael Jun 6 '12 at 21:35
  • 1
    $\begingroup$ This will be my last comment in this thread. Honestly speaking, I fail to see what you want to explain by this “general” argument which cannot be applied to two of three kinds of reductions mentioned in the question. If the generality is not the purpose, then it would be much easier to understand if F is fixed to the set of poly-time reductions and the argument is instantiated with several choices of X. $\endgroup$ – Tsuyoshi Ito Jun 8 '12 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.