Showing a language is in co-NPC

Question

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?

Answer 1

Hint: While it's certainly possible to choose a concrete language and show a reduction from it, in this case it's actually easier to show a reduction from every language in NP.

As a starting point, recall that a language $L$ is in NP iff there exists a polynomial-time verifier for it.

Let $L$ be a language in NP, and let $M$ be a polynomial verifier for it, and let $f(n)\in O(n^k)$ be the runtime of the verifier. Observe that for every word $x$ we have that $x\in L$ iff there exists a witness $y$ such that $M$ accepts $(x,y)$ within $f(|x|)$ steps.

This looks a lot like your language, see if you can complete the proof from here.