Search code examples
complexity-theorynp-complete

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.

Solution

  • 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.