When proving a problem in NP, e.g. k-clique problem defined as k-clique:= {<G,k>| G has a clique of size at least k }, from what I understand is that all we assume for the certificate "c" to be is some string that is of polynomial length of the size of the input.

My question is when designing the verifier, does this verifier (algorithm) only accepts as input a certificate "c" to be a particular desirable string i.e. for the k-clique problem a subset of nodes of G of size k (check below (1)) OR
is this just an idea we put in our head that help us figure out the verifier and in reality "c" can be anything and not necessarly a subset of nodes nor should it be of size k, it could be some string quadratic in size of input?

(1) Hence we choose the Guessed Solution if it exists i.e. a clique of "size K" and if the solution doesn't exist then we choose any subset of nodes of size k and this already will not form a clique, so we are sure the verifier will reject...

Thank you in advance


The second approach is technically the correct interperation. When we say "a verifier gets a certificate $c$ that looks like [...] and computes something", then we actually mean that this verifier checks whether $c$ is of the required format (e.g, check that $c$ is representing a subset of nodes from the graph), and if it isn't it will immediately reject. Otherwise, it will continue to work how you specified it to.


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.