Types of reductions and associated definitions of hardness

Problem Detail: 

Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. The types of reductions:

• Turing reduction: $M_{A}$ can make multiple queries to $O_{B}$.

• Karp reduction: Also called "polynomial time Turing reduction": The input to $O_{B}$ must be constructed in polytime. Moreover, the number of queries to $O_{B}$ must be bounded by a polynomial. In this case: $P^{A} = P^{B}$.

• Many-one Turing reduction: $M_{A}$ can make only one query to $O_{B}$, during its the last step. Hence the oracle response cannot be modified. However, the time taken to constructed the input to $O_{B}$ need not be bounded by a polynomial. Equivalently: ($\leq_{m}$ denoting many-one reduction)

  $A \leq_{m} B$ if $\exists$ a computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

• Cook reduction: Also called "polynomial time many-one reduction": A many-one reduction where the time taken to construct an input to $O_{B}$ must be bounded by a polynomial. Equivalently: ($\leq^{p}_{m}$ denoting many-one reduction)

  $A \leq^p_{m} B$ if $\exists$ a poly-time computable function $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

• Parsimonious reduction: Also called "polynomial time one-one reduction": A Cook reduction where every instance of $A$ mapped to a unique instance of $B$. Equivalently: ($\leq^{p}_{1}$ denoting parsimonious reduction)

  $A \leq^p_{1} B$ if $\exists$ a poly-time computable bijection $f: \Sigma^{\ast} \to \Sigma^{\ast}$ such that $f(x) \in B \iff x\in A$.

  These reductions preserve the number of solutions. Hence $\#M_{A} = \#O_{B}$.

We can define more types of reductions by bounding the number of oracle queries, but leaving those out, could someone kindly tell me if I have gotten the nomenclature for the different types of reductions used, correctly. Are NP-complete problems defined with respect Cook reduction or parsimonious reduction? Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

If I am not wrong, the class #P-Complete is defined with respect to Karp reductions.

Asked By : Pavithran Iyer

Answered By : Kaveh

Your definition of parsimonious reductions is incorrect. You are confusing it with polynomial-time one-one reductions which is a special case of Karp reductions. They don't preserve the number of "solutions". Please see this answer for more about reductions considering the number of certificates.

The rest seems fine although it is usually better to view them in a two dimensional chart:

• the complexity of reduction: computable, polynomial time, logarithmic space, etc.
• type of access: Turing, many-one, one-one, etc.

Are NP-complete problems defined with respect Cook reduction or parsimonious reduction?

$\mathsf{NP}$ hardness and completeness are defined w.r.t. Karp reductions (polytime many-one), not Cook nor parsimonious reductions.

Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

Take the complement of SAT, it is complete for $\mathsf{NP}$ under Cook reductions, it is not believed to be complete for $\mathsf{NP}$ under Karp reductions. Karp reductions include polytime one-one reductions.

the class #P-Complete is defined with respect to Karp reductions

Note that $\mathsf{\#P}$ is not class of decisions problems, it is a class of function computation problems. Its hardness and completeness are usually defined w.r.t. Cook reductions (polytime Turing). See e.g. Arora and Barak, page 346.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3286