# Verifier - Complexity Theory

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

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.

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