A Verifier for a language $A$ is an algorithm $V$ such that $$A=\left\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\right\}.$$

My question about this definition is what is this string $c$ stands for?

Let's say I have a graph and I want to verify if it has a clique. What would be my $c$?


1 Answer 1


A verifier for a language $L$ is an algorithm that accepts as input an instance $x$ of $A$ and a witness $w$, and has the following properties:

  1. The algorithm always halts.
  2. If $x \in A$ then there is a witness $w$ such that the algorithm accepts $\langle x,w \rangle$.
  3. If $x \notin A$ then for all witnesses $w$, the algorithm rejects $\langle x,w \rangle$.

We are often interested in polynomial time verifiers. Such a verifier exists for the clique problem, which is: given a graph $G$ and a parameter $k$, decide whether $G$ contains a $k$-clique. Here is one polynomial time verifier for this problem: it accepts as witness a list $S$ of vertices, and on input $G,k,S$ it accepts if $S$ is a set of $k$ vertices which form a clique in $G$. I'll let you check that this satisfies all the required properties.

  • $\begingroup$ Hi, Thank you for your answer. Can you please elaborate on the "witness" $w$? What do you mean by a "witness"? $\endgroup$
    – Alan
    Commented Jul 4, 2018 at 19:50
  • 1
    $\begingroup$ This is covered in many many online and offline resources. On this site, you can check the following question: cs.stackexchange.com/questions/9556/…. $\endgroup$ Commented Jul 4, 2018 at 19:51
  • $\begingroup$ "Witness" is a semantic rather than syntactic category. A witness is just a string which we think of as a witness. $\endgroup$ Commented Jul 5, 2018 at 12:11

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.