For language $M ⊆ \{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$. The same story about reductions in $L$.
Show that:
(a) reachability problem (in directed graphs) has property $Or$ and $And$ with respect to $L$ reduction.(b) each language in $P$ has both properties with respect to polynomial reductions.
(c) each language in $NP$ has both properties with respect to polynomial reductions.
This is content of exercise. My problem is that I am not sure if I correctly understand it.
Let's consider (a)
We know that reachibility in directed (and undirected) graphs is in $L$. However, adjacency matrix (or arbitrary form of input graph) is contaminated with $\#,0,1$. For example $And$ generates something like:
$\#[graph]\#[graph]\#[graph]\#[graph]$, where $[graph]$ is input graph (for instance adjacency matrix).
We should shell $[graph]$ and launch on it well known algorithm for reachability in digraph. So this digging into $[graph]$ must be done in logspace, however it is seems to be easy. We only need counter to find begin position and end position of input graph (in $AND$ case - find first and second $\#$), $Or$ is also easy (when it comes to digging into $[graph]$
Can you tell me if I properly understand this exercise? In particular if part (a) is ok ?
Edit
After discussion in comments with @TStancek
(a)
I have some doubts about proper solution - simply I don't know what exactly reduction means as I think.
First attempt:
Let $K$ will be machine for solving reachibilty in directed graphs in logspace. We launch $K$ on each word between $\#s$. Our reduction/machines captures trying to read from input tape by $K$ and provide proper field of input (it is easy to do in logspace).
Second attempt:
This one look like reduction. In logspace transform input graph and launch on it (transformed graph) $K$.
What attempt is correct ? And how to transform it ?
This might be incorrect answer, because I am unsure here. So please let me know in case I am wrong and I will delete it or upgrade in case I am not far from correct answer. And also it is a partial answer, but I cannot wrote it all in comment.
To me it seems like the quest is to inspect words between $\#$ and in case of And test whether every such word is in M and in case of Or at least one word is in M.
So, in a) and case of And every graph needs to be in M, so in every one we need to reach our destination. So I would connect end of one graph with the start of the succeeding graph, thus creating connection of all the graphs through the points that need to be reached. And the resulting graph can reach from the starting point of the first graph to the ending point of the last graph only in case all the graphs could reach there respective pairs of points.
In case of Or, only one graph needs to be in M, so I would take a starting point and connected it to all starting points in each graph between individual $\#$, and one common end point, to which I would add edge from every ending point. If at least one of the graphs is in M, there is a way from added starting point to the added ending point.
All of that would require simple checker for the validity of a string, that it really describes a graph. And in case it does not, it would replace the graph with a starting and ending point, but with no edge between them. It is the simplest graph not in M that suits the needs of the reduction procedure.
The rest would probably be something similar, only using P- and NP-complete problems.
EDIT: Probably better is in case of $And$ test, whether given graph has a path from start to end and reject on the first graph not meeting this condition. And in case of $Or$ do the same, use a algorithm check individual graphs between $\#$ and accept on first found such graph.
That can be done also for P, simply run polynomialy reduce the individuals words to their equivalent in some P-omplete language a test it using this P-complete language the same way as in a) (reject on first failure vs accept on first success).
But the NP-complete already has to be reduced, because no known polynomial algorithm can solve it.