15
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry, I seem to I have interchanged the "Karp reduction" and "Cook reduction" terminology. If I interchange it, then it matches your responses. Thanks. Regarding parsimonious reductions, are you saying that they do not preserve the number of "solutions" ? If so, I see in Theorem 17.10 of Arora & Barak (Page 299) that parsimonious reductions do indeed preserve the number of solutions. Another reference: (cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf) $\endgroup$
    – Pavithran Iyer
    Aug 22, 2012 at 22:37
  • $\begingroup$ Here it says a parsimonious reduction from L to SAT, maps every instance x of L to a unique instance of SAT (that is, reduction map is one-one): [cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf] . Isn't it right to assume that if the number of solutions are preserved by a reduction, then the map is one-one ? $\endgroup$
    – Pavithran Iyer
    Aug 22, 2012 at 22:48
  • $\begingroup$ @Pavithran, what you wrote in your question was not the definition of parsimonious reductions. For the answer, see the exercise 2.13 in their book. $\endgroup$
    – Kaveh
    Aug 22, 2012 at 23:03
1
$\begingroup$

The definition of Karp reduction is incorrect. A Karp reduction is a polynomial-time Turing reduction in which the oracle $O_B$ is called exactly once, during the reductions last step.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Specifically, the definitions of Cook and Karp reductions have been switched. $\endgroup$
    – David Richerby
    Dec 14, 2018 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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