patternMinor
Show that NP is closed under concatenation
Viewed 0 times
showclosedunderthatconcatenation
Problem
Show that NP is closed under concatenation.
This is a homework problem and I would appreciate some guidance. I began by saying the following:
Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be verifiers for $A$ and $B$, respectively.
Is it as simple as saying build two NTMs $M_1$ and $M_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?
This is a homework problem and I would appreciate some guidance. I began by saying the following:
Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be verifiers for $A$ and $B$, respectively.
Is it as simple as saying build two NTMs $M_1$ and $M_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?
Solution
No, it's not that simple. You need to explain what you mean by concatenate $M_1$ and $M_2$. The machines $M_1,M_2$ don't output strings that can be concatenated.
You need to describe what the concatenated machine $M$ does. On input $x$, how does it use the machines $M_1,M_2$? If you run $M_1,M_2$ on the entire input $x$ it won't help you to decide the concatenated language, so you'll have to be more industrious.
You need to describe what the concatenated machine $M$ does. On input $x$, how does it use the machines $M_1,M_2$? If you run $M_1,M_2$ on the entire input $x$ it won't help you to decide the concatenated language, so you'll have to be more industrious.
Context
StackExchange Computer Science Q#66717, answer score: 2
Revisions (0)
No revisions yet.