2
$\begingroup$

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$?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi, Thank you for your answer. Can you please elaborate on the "witness" $w$? What do you mean by a "witness"? $\endgroup$ – Alan Jul 4 '18 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$ – Yuval Filmus Jul 4 '18 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$ – Yuval Filmus Jul 5 '18 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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