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.