The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more:

Suppose that A is NP Complete, but B is in P. I claim that AB is NP Complete and BA is NP Complete as well. To see this, assume first that AB is in P, and let X and Y be polynomial time algorithms for B and for AB, respectively. “Concatenating” X and Y as follows yields an algorithm Z for A:

Given L, test L using X;

if X outputs “yes”, test using Y;

if Y yields “yes”, output “no” and stop;

if X yields “no”, output “no” and stop; output “yes” otherwise and stop.

This algorithm Z runs in polynomial time, because if the (polynomial time) complexity exponent of X is k and the (polynomial time) complexity exponent of Y is n, then this algorithm clearly has (polynomial time) complexity exponent m=max(k,n). This would provide a proof that P=NP, so AB is NP Complete.

Now suppose that BA is in P. This time, let Y’ be a polynomial time algorithm for BA and let X be as above. We construct an algorithm Z’ for A, as follows:

Given L, test L using X;

if X outputs “yes”, test using Y’;

if Y yields “no”, output “yes” and stop;

if X yields “no”, test using Y’; if Y yields “no”, output “yes” and stop;

output “no” otherwise and stop.

This yields a polynomial time algorithm for A, and so again, this would entail that P=NP, so BA also is NP Complete.

+++++++++End of Example++++++++++++

While I don’t see anything wrong with the above at the moment, perhaps I have a mistake or complexity miscalculation? …because for a while as I was writing the second algorithm, I began to think it was odd and perhaps impossible that I can be right about BA also being NP Complete…

Like I said, I’m somewhat new to this area, so feedback would be appreciated.