Hardness of FNP vs Choice of Verifiers

Question

A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be finding the certificate $y$ (if exist).

However, the choice of verifier could be arbitrary, for example, the verifier for $HAM-PATH$ problem could be

1. Determinig whether the computation path of TM configurations is valid and reaches accepting state. (The Cook-Levin way).
2. Determine whether a path of input graph is Hamiltonian. (The natural way)

In order to make this definition "natural", we should probably show that, undere these different choice of verifier, the definition remains equivalent, i.e. the problem do not suddenly become harder/easier just because we introduce a different verifier.

So here's my question: Is the choice of verifier independent with hardness of its functional problem? How do we justify this?

Answer 1

No (unless $P=NP$). Consider a language $L$ that is in $P$, say, $L$ is the language of prime numbers.

Suppose $V_1$ works as follows: $V_1(x,y_1)$ ignores $y_1$ and checks directly whether $x$ is prime, and if so, outputs 1; otherwise it outputs 0.

Suppose $V_2$ works as follows: $V_2(x,y_2)$ interprets $x$ as a 3CNF formula and checks whether $y_2$ is a satisfying assignment for it; then it checks whether $x$ is prime; and if both are true, it outputs 1, otherwise it outputs 0.

Both verifiers define the same language, namely, $L$.

However, given $x$, the problem of finding $y_1$ that's accepted by $V_1$ can be solved in polynomial time; but the problem of finding $y_2$ that's accepted by $V_2$ is NP-hard. So, assuming $P \ne NP$, those two function problems have different hardness.