3
$\begingroup$

We define xor operation on languages $L,M\subseteq \{0,1\}^*$:
$$L\oplus M = \{u\oplus v :|u|=|v|, u\in L, v\in M\}$$ $\oplus$ is defined as xor on postions, for example: $001\oplus 100=101$ Show that there exist languages $L,M\in PTIME$ such that $L\oplus M\in NP complete$

It is hard to me. I have been thinking a lot about it. My intuition is:

Write the problem as equations system and reduce 3-SAT to it. But, I am not sure if it is ok and, if yes, how to solve it.

$\endgroup$
  • $\begingroup$ You don't need to reduce the 3SAT to $L\oplus M$ in order to prove $L\oplus M \in NP$. It is enough to show that $x\in L\oplus M$ is verifiable in polynomial time on a deterministic TM. However, the reduction of 3SAT to $L\oplus M$ would also imply $L\oplus M \in NP$, but the latter may be harder to demonstrate. $\endgroup$ – fade2black Aug 10 '17 at 23:02
  • $\begingroup$ I edited my post $\endgroup$ – Carol Aug 10 '17 at 23:11
  • 2
    $\begingroup$ Now, try to solve it yourself. First show that if both $L$ and $M$ in $PTIME$ then $L\oplus M$ is in $NP$. This part is easy - you don't need to come up with a concrete $L$ and $M$. Then try to come up with concrete $L$ and $M$ such that an $NP$-complete (maybe 3SAT) problem is reduced to $L\oplus M$. That part is harder. If you get stuck you can post what you have done and where you have got stuck. $\endgroup$ – fade2black Aug 10 '17 at 23:17
2
$\begingroup$

This seems like a rather difficult question. Here is one approach.

Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages: $$ \begin{align*} L_1 &= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}, \\ L_2 &= \bigcup_{n=1}^\infty \{ x0^{8n^3}y : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}. \end{align*} $$ These two languages are clearly in P, and so their XOR is clearly in NP. However, $$ (L_1 \oplus L_2) \cap \bigcup_{n=1}^\infty \{0^ny^2 : |y|=8n^3\} = \bigcup_{n=1}^\infty \{0^n y^2 : |y|=8n^3, y \text{ is satisfiable}\}, $$ showing that $L_1 \oplus L_2$ is NP-complete.

$\endgroup$
  • $\begingroup$ Why $L_1$ is in PTIME ? After all, in this way I can solve $\phi$ in 3CNF in P: $L_1= \{x : \text{$x$ is an assigment satisfying given $\phi$ 3CNF formula} \}$ $\endgroup$ – Haskell Fun Aug 11 '17 at 12:21
  • $\begingroup$ Your example is a finite language and so in $\mathsf{P}$. In fact, it has a constant time algorithm. The algorithm reads the first $n$ bits on the tape, and then can immediately answer Yes or No. $\endgroup$ – Yuval Filmus Aug 11 '17 at 12:37
  • $\begingroup$ I understand that my approach (below) is not ok, because finite languages are regular. However, your $L_1$ is thing that I don't understand it. I can't see how you can do it in PTIME. $\endgroup$ – Haskell Fun Aug 11 '17 at 17:47
  • $\begingroup$ You can check whether a truth assignment satisfies a formula in polynomial time. $\endgroup$ – Yuval Filmus Aug 11 '17 at 19:02
  • 1
    $\begingroup$ Could this be simplified conceptually by choosing $L_1 = \bigcup \{xy :|x|=n,|y|=8n^3, x \text{ is an assignment satisfying the 3CNF } y\}$ and $L_2= \bigcup \{x0^{8n^3}:|x|=n \}$. In that way $L_2$ just hides the assignment . $\endgroup$ – Hendrik Jan Aug 23 '17 at 15:24
1
$\begingroup$

I have other idea, I am not sure if it is correct:
Let $k$ will be number of clauses and $n=5$ number of variables. I reduce $3-$SAT problem, for each clause $c_i=(x_1, x_3, \neg x_5)$ I create language $$L_i= \{1\{0,1\}\{0,1\}\{0,1\}\{0,1\},\{0,1\}\{0,1\}1\{0,1\}\{0,1\}, \{0,1\}\{0,1\}\{0,1\}\{0,1\}0 \}$$
So $L_i$ contains patterns which satisfy $c_i$. Of course $L_i\in P$.
Let $$L=L_1\cdot ...\cdot L_k$$, $$M=\{(\{0,1\}^n)^k\}$$
Hence, $M$ contains all possible assigments reapeted $k$ times. Now, we can check if $0^{kn}$ belongs to $L\oplus M$ in order to check if given $3CNF$ formula is satisfable. The meaning is that $0^{kn}\in M$ does mean that each clause agree with some assigment (agreeing corresponds to satisfability)

$\endgroup$
  • $\begingroup$ The language $L \oplus M$ is finite, and so trivially in $\mathsf{P}$. $\endgroup$ – Yuval Filmus Aug 11 '17 at 11:17
  • $\begingroup$ @YuvalFilmus in 3SAT problem there are also finite numbers of assigments, however 3SAT is in NP. Where is the key ? $\endgroup$ – Haskell Fun Aug 11 '17 at 11:56
  • $\begingroup$ Your language $L \oplus M$ is finite. The language of satisfiable 3CNF is infinite. The key is that $L,M$ in your case depend on a formula. What you want is a single pair $L,M$ that would work for all formulas. $\endgroup$ – Yuval Filmus Aug 11 '17 at 12:36
  • $\begingroup$ yes, but @HaskellFun has to take a formula $F$ and convert it to that problem. Why is it not ok? $\endgroup$ – Carol Aug 11 '17 at 13:30
  • $\begingroup$ @Carol The construction just doesn't work. $\endgroup$ – Yuval Filmus Aug 11 '17 at 19:13

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.