Skip to main content
MathOverflow

Return to Question

deleted 1 characters in body
Source Link
Stefan.M
Stefan.M
  • 153
  • 1
  • 4

I have this problem,

Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:

$L_1 \oplus L_2 = \{x | x$$L_1 \oplus L_2$ = {x | x is in exactly one of $L_1, L_2\}$$L_1, L_2$}

I do not have a clue how to show it. We know that $L_1 \cap L_2 \in NP$ is unknown. So for that reason it is reasonable to ask only that instance of the problem. From my point of view, if $L_1 \in NP$ there is some verifier for that language which runs in polynomial time. We have such verifier for the second language $L_2$ too. My proposal of the machine M which decides $L_1 \oplus L_2$ is as follows:

Let's have

M = "for the input x:
1. copy x on the second tape
2. run x on M_1 on the first tape
3. if M_1 accepts, (otherwise go to 4.)
    3a) run x on M_2
    3b) if  M_2 accepts, M rejects 
4. run x on M_2, if M_2 accepts, M accepts, otherwise M rejects.

I do not know the relation of this with the co-NP class ... Is my reasoning right? This machine works like a charm for languages $L_1,L_2 \in P$. Does it hold also for that intersection?

Thank you a lot

I have this problem,

Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:

$L_1 \oplus L_2 = \{x | x$ is in exactly one of $L_1, L_2\}$

I do not have a clue how to show it. We know that $L_1 \cap L_2 \in NP$ is unknown. So for that reason it is reasonable to ask only that instance of the problem. From my point of view, if $L_1 \in NP$ there is some verifier for that language which runs in polynomial time. We have such verifier for the second language $L_2$ too. My proposal of the machine M which decides $L_1 \oplus L_2$ is as follows:

Let's have

M = "for the input x:
1. copy x on the second tape
2. run x on M_1 on the first tape
3. if M_1 accepts, (otherwise go to 4.)
    3a) run x on M_2
    3b) if  M_2 accepts, M rejects 
4. run x on M_2, if M_2 accepts, M accepts, otherwise M rejects.

I do not know the relation of this with the co-NP class ... Is my reasoning right? This machine works like a charm for languages $L_1,L_2 \in P$. Does it hold also for that intersection?

Thank you a lot

I have this problem,

Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:

$L_1 \oplus L_2$ = {x | x is in exactly one of $L_1, L_2$}

I do not have a clue how to show it. We know that $L_1 \cap L_2 \in NP$ is unknown. So for that reason it is reasonable to ask only that instance of the problem. From my point of view, if $L_1 \in NP$ there is some verifier for that language which runs in polynomial time. We have such verifier for the second language $L_2$ too. My proposal of the machine M which decides $L_1 \oplus L_2$ is as follows:

Let's have

M = "for the input x:
1. copy x on the second tape
2. run x on M_1 on the first tape
3. if M_1 accepts, (otherwise go to 4.)
    3a) run x on M_2
    3b) if  M_2 accepts, M rejects 
4. run x on M_2, if M_2 accepts, M accepts, otherwise M rejects.

I do not know the relation of this with the co-NP class ... Is my reasoning right? This machine works like a charm for languages $L_1,L_2 \in P$. Does it hold also for that intersection?

Thank you a lot

Source Link
Stefan.M
Stefan.M
  • 153
  • 1
  • 4

symmetric difference of languages - both are in NP and coNP

I have this problem,

Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:

$L_1 \oplus L_2 = \{x | x$ is in exactly one of $L_1, L_2\}$

I do not have a clue how to show it. We know that $L_1 \cap L_2 \in NP$ is unknown. So for that reason it is reasonable to ask only that instance of the problem. From my point of view, if $L_1 \in NP$ there is some verifier for that language which runs in polynomial time. We have such verifier for the second language $L_2$ too. My proposal of the machine M which decides $L_1 \oplus L_2$ is as follows:

Let's have

M = "for the input x:
1. copy x on the second tape
2. run x on M_1 on the first tape
3. if M_1 accepts, (otherwise go to 4.)
    3a) run x on M_2
    3b) if  M_2 accepts, M rejects 
4. run x on M_2, if M_2 accepts, M accepts, otherwise M rejects.

I do not know the relation of this with the co-NP class ... Is my reasoning right? This machine works like a charm for languages $L_1,L_2 \in P$. Does it hold also for that intersection?

Thank you a lot