3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 14 at 20:58
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Taylor Huang Apr 18 at 17:33
  • $\begingroup$ @TaylorHuang, 1. Good question. I don't know. 2. No, you shouldn't expect any such unconditional conclusion. If P=NP, then the answer is yes; if P!=NP, then the answer is no. So an unconditional answer would yield a resolution of the P vs NP problem. $\endgroup$ – D.W. Apr 18 at 18:50

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.