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.


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.