Meaning of ⟨_⟩ in the context of verifiers

Question

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?

Answer 1

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.