Is there any known $NP$-complete problem which hardness proof is non-constructive.

A constructive $NP$-completeness proof is a proof that $L_1\leq_p L_2$ by a reduction $r$ and from the argument therein, one can extract two polynomial-time algorithms $f$ and $g$ such that:

For every instance $x\in L_1$, given a certificate $w_1$ for $x$, we must have that $w_2=f(w_1)$ is a certificate for $r(x)\in L_2$

For every instance $x\in L_1$, given a certificate $w_2$ for $r(x)\in L_2$, we must have that $w_1=g(w_2)$ is a certificate for $x\in L_1$.

In $NP$-completeness result, that does not describe $f$ and $g$, we can say that it is a non-constructive proof. Given a certificate for an instance of $L_1$, one does not know how to construct a certificate for the corresponding instance of $L_2$ and vice versa.

In a sense, the proof only establishes the existence of corresponding certificates.

More specifically, do we have an existence-only proof for some $NP$-complete problem?

  • $\begingroup$ You might want to have a look at this question on CSTheory. $\endgroup$
    – Juho
    Commented Oct 11, 2018 at 19:18
  • $\begingroup$ That is the non-constructivity of the existence of a Karp reduction. Here, a Karp reduction must be presented already. $\endgroup$ Commented Oct 12, 2018 at 3:39

1 Answer 1


If worst-case one-way permutation exists (which exists iff. $P\neq UP\cap coUP$, proven here), then there exists inefficient reduction proof for some $NP$-complete problem.

We denote $\pi$ the one-way permutation above.

Specifically, for each proven $NP$-complete $L$, we can define:

$PERMUTED-WITNESS(L)=\{\pi(x)\mid x\in L\}$

with the certificate for $y\in PERMUTED-WITNESS(L)$ as: $(x,c)$ where $\pi(x)=y$ and $\pi(c)$ is a certificate for $x\in L$ (the "original" certificate). In other words, $c$ is the pre-image of the "original" certificate.

So, given a certificate $c'$ for $x\in L$, we cannot efficiently find $c$ (the pre-image of $c'$) for $\pi(x)\in PERMUTED-WITNESS(L)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.