Is a reduction enough for proving NP-complete or do I need a transformation?

If I have a decision problem开发者_开发技巧 A, and wish to show that it is NP-complete. Is it enough to prove that another NP-complete problem polynomially reduces to A, or must I show that another NP-complete problem polynomially transforms to A?

That is, can I show that

procedure solve_SAT
...
call solve_A
call solve_A
call solve_A
...
end

or am I only limited to a single use of solve_A, as shown

procedure solve_SAT
input  = ...
result = call solve_A(input)
return result
end

I find some sources say the former while other sources say the latter, and it is a bit confusing to me.

Suppose you have a decision problem A and you wish to prove that it is NP-Complete then the way to do it is, take an existing NP-Complete problem and reduce it to A. What I mean by reduction here is a polynomial time reduction.

So suppose you wanted to show that 3-SAT is NP-Complete then you can show a reduction from the SAT problem.

The important thing to note here is that the reduction must be poly-time. It doesn't matter whether you call solve_A() multiple times. You can choose to call solve_A() multiple times as long as you make a polynomial number of calls to solve_A().

Why does it work? You can prove it by contradiction. Suppose you had a poly-time algorithm for 3SAT. Then you could solve SAT also in poly-time. Since a polynomial number of calls to a polynomial function is still polynomial. So unless P=NP, this would imply that SAT can also be solved in polynomial time using the newly discovered poly-time algorithm for 3SAT. But we know that SAT is NP-Complete, hence 3SAT must also be NP-Complete.

In short, to show NP-Completeness two things are required.

Existence of a certificate. A reduction from an existing NP-Complete problem.

If your procedure for solve_SAT uses only a constant number of calls to solve_A, then a polynomial-time algorithm for A would imply a polynomial time algorithm for SAT. This doesn't meet the exact definition of SAT, but it would imply that no polynomial-time algorithm for A exists unless P = NP.

The definition for NP-completeness settled upon today is that a polynomial many-one or Karp reduction from a known NP-complete problem to your problem is needed to show NP-completeness. This is also known as a polynomial transformation and corresponds to your example where you only get to call your solve_A function once.

Your other example, where you can call solve_A a polynomial number of times corresponds to the Turing or Cook reduction. The existence of a Turing reduction from an NP-complete problem to your problem is proof of the NP-hardness of your problem, which is thought to be a different property than NP-completeness.