A verifier for a language A is an algorithm V, where $$A = \{w \mid V \text{ accepts $\langle w,c \rangle$ for some string $c$}\}$$ ($c$ is called a certificate or proof)

What's the definition of $\langle , \rangle$ here?

  • 1
    $\begingroup$ Not every question is about P vs NP. I think you should read up on the basics, starting with e.g. our reference questions. Anyway, the definition is probably given in the same source on an earlier page. What is your source, by the way? $\endgroup$
    – Raphael
    Sep 18 '15 at 17:45

Any reasonable definition would do (I'll provide a formal definition later on). One simple definition, when $w,c$ are strings over some alphabet $\Sigma$ which doesn't contain the space character, is that $\langle w,c \rangle$ consists of $w$, a space, and $c$.

More generally, suppose that $\langle w,c \rangle_1$ and $\langle w,c \rangle_2$ are two definitions of the pairing function such that:

  1. There exists a polytime function $f$ such that $f(\langle w,c \rangle_1) = \langle w,c \rangle_2$.
  2. There exists a polytime function $g$ such that $g(\langle w,c \rangle_2) = \langle w,c \rangle_1$.

Then if we define NP using $\langle,\rangle_1$ and $\langle,\rangle_2$ we obtain the same class. A reasonable definition is one that satisfies (1) and (2) for the pairing function I described above.

This sort of situation happens often in complexity theory. When the details of the input representation don't make a difference, we don't bother specifying them exactly. That's because we never actually refer to these details, so they are "too much information". You only need to worry about such details when you're actually programming, or when you're dealing with very weak complexity classes, for which converting between different input representations can be difficult.


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.