# Hardness of FNP vs Choice of Verifiers

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?

• I think you're asking: given two verifiers $V_1,V_2$ for the same language $L$ (possibly with different certificates), consider the problem of, given $x$, finding a certificate $y_i$ for $x$ accepted by $V_i$; is this problem equally hard for $i=1$ as for $i=2$? Let me know if I've misunderstood what you are asking. – D.W. Apr 14 at 20:58

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.
• I think it kind of make sense, just wonder 2 things: 1. Could some mild conditions be added in to avoid this? 2. Could we have unconditional conclusion that search under verifiers $V_1, V_2$ are indeed different? – Taylor Huang Apr 18 at 17:33