I'm preparing for a test, and I've stumbled across the next question:
"Prove that the complexity class NP ∩ co-NP is closed under concatenation."
So my idea was that I know that a language $L∈ (NP ∩ co-NP)$ iff both $L$ and $\bar L$ belong to NP. So I know that I need to find a non-deterministic turing machines that runs in polynomial time and is solvable for $L1L2$ and $\overline {L1L2}$.
For $L1L2$ I have an idea, using the machines that are given to me already by knowing that L1 and L2 are in NP, I can build a Turing machine that accepts when both of their machines accept, and declines otherwise.
My problem now is with $\overline {L1L2}$, I thought about two approaches:
- If I do the same idea which I did with $L1L2$, and use the turing machines that given to me by $\overline {L1}$ and $\overline {L2}$ but I don't feel it's right - since I don't think that complement of concatenation is concatenation of complements.
- Taking the TM I built in the first step, and basically swapping the accept and decline, which seems right but doesn't it prove that $NP = co-NP$ ? Because then I could take every problem in $NP$ and swap the accept/decline and and make it decidable.
I would be glad to hear of ideas or help to fix my understanding of the things I proposed. Thank you!