Showing a language is in co-NPC
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.