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?


1 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.

  • $\begingroup$ i am familiar with verifiers but i only used them to prove that a language is in NP. you are saying i should do a reduction from a general language in NP and that would suggest that every language in NP has a reduction to L so it is in NPC? but i don't understand how to use the verifier to do such proof. let's say i have a general language A in NP, which has a polynomial verifier M. is the idea to use M to conduct a polynomial verifier to L? $\endgroup$
    – bar
    Commented Aug 17, 2013 at 18:52
  • $\begingroup$ Yes, that's the general idea. I added some details to the answer. $\endgroup$
    – Shaull
    Commented Aug 17, 2013 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.