I need to prove that this language is in co-NPC: $\{ \langle M,x,1^n \rangle \mid M $ is a TM and for all $c \in \Sigma^*$ , $M$ accepts in $ $$n$ steps when given $(x,c)$ as input $\}$.
I tried to do so by showing that the complement is in NPC, that is $\{ \langle M,x,1^n \rangle \mid M $ is a TM and there exists $c \in \Sigma^*$ , s.t $M$ doesn't accepts in $n$ steps when given $(x,c)$ as input $\}$.
I can prove that it's in NP by giving a polynomial non-deterministic algorithm, but I get stuck in the reduction part and don't know from which language in NPC to do a polynomial reduction and how. Does anybody know how do deal with such reduction?