Let $L$ be an NP-complete language. Let $W(x)$ denote the set of (polynomially length bounded) witnesses that certify $x\in L$. That is, $x\in L$ if and only if there exists a $w$, such that $w\in W(x)$. For example, if $x$ encodes a SAT instance, then $W(x)$ contains all satisfying truth assignments of the formula $x$.

Let us assume that every witness has even length, and define the following new language: $$L'=\{x\#u\:|\: \exists v \; \mbox{such that}\; |u|=|v|\; \mbox{and}\; uv\in W(x)\}$$ where $\#$ is a symbol that is only used for separation, it does not occur in $x$ and $u$.

The meaning of this construction is that with every input $x$, the new language $L'$ reveals the first half of a witness. In this sense, $L'$ is "easier" than $L$, because we only need to find the second half of the witness, its first half is already given. On the other hand, finding the second half still appears hard. For example, if for a SAT instance half of a satisfying truth assignment is given, it is still hard to find the other half, since after substituting the given truth values, in general we are still left with a polynomial sized formula to satisfy.

Question: Is there any condition which guarantees that $L'$ remains NP-complete?

Note: In general, $L'$ does not have to remain NP-complete. For example, if each witness is constructed such that its second half is only a dummy filler (such as all 0), then $L'\in {\bf P}.$

  • 2
    $\begingroup$ Why do you think that the pad technique doesn't work for (probably all) NP-complete problems? For example, from SAT: if $\varphi$ is a formula on $n$ variables, add $n$ more dummy variables $x_{n+1},..,x_{2n}$ IN FRONT OF IT and single-variable clauses $x_{n+1},...,x_{2n}$ in front of it. Call $\varphi'$ the new formula. Then $\varphi'\#1^n \in SAT'$ if and only if exists $v$ s.t. $1^{n}v \in W(\varphi')$ for some $v$, i.e. if and only if $\varphi'$ is satisfiable; but $\varphi'$ is satisfiable if and only if $\varphi$ is satisfiable. Informally "place" the dummy variables in the right place. $\endgroup$ – Marzio De Biasi Mar 22 '16 at 8:02
  • $\begingroup$ @MarzioDeBiasi Depending on how we do the padding, we can certainly control whether $L'$ remains NP-complete or falls into P. However, I assume we are only given a polynomial time algorithm that can decide whether a witness is correct or not, that is, we can efficiently decide membership in $W(x)$, but we cannot control how the witnesses are constructed. I am interested in whether in this case can we say anything in general about how the complexity changes if half of a witness is revealed. $\endgroup$ – Andras Farago Mar 22 '16 at 14:27
  • 3
    $\begingroup$ At this level of generality, I doubt there is any condition beyond simple reformulations. For example, generalizing from SAT, a "composability" or "closed-under-product" property would suffice, such as: there is an honest poly-time function $f(x,y)$ such that for every $(x,y) \in \Sigma^*$, $W(f(x,y)) = W(x)W(y)$ (where the latter denotes $\{ww' | w \in W(x), w' \in W(y)\}$). $\endgroup$ – Joshua Grochow Mar 22 '16 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.