1
$\begingroup$

For language $M \subset \{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$.

Show that each language in $P$ has both properties with respect to polynomial reductions.

Please hint me because I cannot come up with an idea how to show it.

$\endgroup$

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.