In the paper Complexity of the Frobenius Problem by Ramírez-Alfonsín, a problem was proved to be NP-complete using Turing reductions. Is that possible? How exactly? I thought this was only possible by a polynomial time many one reduction. Are there any references about this?
Are there two different notions of NP-hardness, even NP-completeness? But then I am confused, because from a practical viewpoint, if I want to show that my problem is NP-hard, which do I use?
They started the description as follows:
A polynomial time Turing reduction from a problem $P_1$ to another problem $P_2$ is an algorithm A which solves $P_1$ by using a hypothetical subroutine A' for solving $P_2$ such that, if A' were a polynomial time algorithm for $P_2$ then A would be a polynomial time algorithm for $P_1$. We say that $P_1$ can be Turing reduced to $P_2$.
A problem $P_1$ is called (Turing) NP-hard if there is an NP-complete decision problem $P_2$ such that $P_2$ can be Turing reduced to $P_1$.
And then they use such a Turing reduction from an NP-complete problem to show NP-completeness of some other problem.