Not necessarily! Your sub-problem A could be NP-complete, but for example it might not get triggered at all for any input to C! Or for example a poly-time process on the input before calling A, puts the input of A in a condition that it can be processed with a poly-time algorithm.

To be able to say your problem C is in NP-complete, you should be able to say that it is as hard as another NP-complete problem. To establish this, you need to make a reduction from a NP-complete problem (e.g. SAT) to C. In other words, if your main problem can be seen as the core solving part of another NP-complete problem, then your problem is NP-complete as well (SAT(f) = C(ploy-time-transform(f))). But not the other way around (if a part of C is NP-complete, you can not say anything about NP-completeness of C).

I don't really understand why this argument applies. Let's consider the initial situation where C is the so called main problem and A is a sub problem which is proofed to be np-complete. So all instances of A are also instances of C. Why isn't it then possible to take an instance of problem A and identically map it by means of f to an instance of C, so we can reduce A to C? Its then obvious why " I is 'yes' instance of A f(I) is 'yes' instance of C " applies since A with instance I is literally the same problem as f(I) with C. This would imply A

Julian Walter Considering your definition of sub-problem, yes, I agree that "C" is NP-complete if "A" is NP-complete. I interpreted the phrasing "sub-problem (which is a part of a main problem)" in the question title not in that way. So I guess OP needs to make it clear what he meant. Thanks.