Prove that each language in $NP$ has both properties with respect to polynomial reductions.

Question

For language $M ⊆ \{0, 1\}^*$ lets denote $And(M) = \#(M\#)^*$ and $Or(M)=\#\{0,1,\#\}^*\#M\#\{0,1,\#\}^*\#$. We can say that language has $AND$ ($OR$) property with respect to polynomial reductions if there exists polynomial reduction from $AND(M)$$(OR(M))$ to $M$. The same story about reductions in $L$ (logspace).

Show that:
each language in $NP-complete$ has both properties with respect to polynomial reductions.

Can you help me solve it ? I have no idea.

Edit
Clarification of symbols: $M$ is language over $\{0,1\}$, for example $M=0^n1^n=\{01, 0011, 000111,..\}$
$And(M)=\#(M\#)^* = \{\#, \#00001111\#01\#000111\#000111\#0011\#, \#0011\#01, \#01,...\}$

$\{0,1,\#\}^* = \{0111100\#\#\#\#, \#\#\#\#, \epsilon, 01010101, 01010\#01\#, 00000,11,....\}$

Answer 1

Hint: try doing it for $M = \mathsf{SAT}$ first.

Answer 2

And(M): You have a problem $M$. You can reduce it to 3-SAT. Now, you can "convert" your $And(3-SAT)$ to conjuction of formulas. I mean for example: $$And(3-SAT) = \#(x_1 \vee x_2 \vee x_3)\#(x_4 \vee x_5 \vee x_6)\# \\ \text { to } (x_1 \vee x_2 \vee x_3) \wedge \#(x_4 \vee x_5 \vee x_6)\#$$

And now you can convert that to $M$ (becasue $M$ is NP-complete) and then run machine for $M$ for that.

---

Or(M): You can the similar thing as above. When you make a conjuction of formulas you use $\vee$ instead of $\wedge$. For example: $$And(3-SAT) = \#(x_1 \vee x_2 \vee x_3)\#(x_4 \vee x_5 \vee x_6)\# \\ \text { to } (x_1 \vee x_2 \vee x_3) \vee \#(x_4 \vee x_5 \vee x_6)\#$$

Now, you have not a 3-CNF formula but you can convert it to satisfability-equivalent 3-CNF formula in polynomial time.

Then you also convert it to $M$.

---

I am not sure whether it is correct. Maybe does someone verify it?

Answer 3

Since NP contains $M$, contains regular languages and is closed under concatenation and Kleene star, languages $And(M) = \#(M\#)^*$ and $Or(M)=\#\{0,1,\#\}^*\#M\#\{0,1,\#\}^*\#$ are in NP.

Since $M$ is NP-hard, there is a reduction from $And(M)$ to $M$ and from $Or(M)$ to $M$.