Generally the "threading" functions expect things to have the same shape. If I understand your situation, you have one set, XX that you want to pair with each of two other sets, contained in TT. Since the shapes aren't the same (length 1 versus length 2), it will be awkward and convoluted to get threading to work. You could just map:
XX = {P1, P2, P3, P4};
TT = {{P1}, {P2, P3}};
Map[Complement[XX, #] &, TT]
(* {{P2, P3, P4}, {P1, P4}} *)
You don't need SetDelayed (i.e. :=), just Set (i.e. =) works fine. Also, you had an extra layer of List in TT.
