Question

1. [1 points Let L S 10,1 and L E P. For strings x, y e 0,1 of the same length, let x田y denote the bitwise XOR of x and y-eg., 1000田0111 = 1111. Let ㈣ denote the length of z. Let L* L' = {x : 3y, y has lxl/2 ones and x89 E L). Show that L* E NP

Answer 1

Given information: .

Definition: $L^* = \{x: \exists y, \#_1y = \lvert x \rvert / 2, x \oplus y \in L \}$

Claim: $L^* \in NP$ .

Proof: To prove this, it is sufficient to come up with a certificate for this language, and a polynomial verifier. Any word in the language should have a certificate, and none for words not in the language.

This definition of the language already suggests the following as the certificate: .

The verifier does the following: on input , and certificate , it checks the length of them are equal and that y has exactly as many ones as half the length of x. This takes only linear time. Then it calculates $x \oplus y$ . This takes linear time as well.

Finally, given that $L \in P$ , there is a polynomial time machine M which accepts exactly the words in L. The verifier runs M on $x \oplus y$ and accepts if and only if it is accepted.

It is clear that the verifier accepts if and only if such a certificate exists, and the certificate exists only for the words in the language. This completes the proof.

Comment in case of any doubts.