-1

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 ?

Community
  • 1
Haskell Fun
  • 113

1 Answers1

0

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.

TStancek
  • 1,027
  • 5
  • 14
  • $M\in P$. Why did you mention P-complete problems. It should work: And: for each word $w$ between $#s$ launch polynomial machine for $M$ and check if it accept $w$. Or: Check if any of word $w$ between $#s$ is accepted by $M$. In both cases it requires $|input|\times O(|input|^k)$ what is polynomial. 2. $M\in NP$. In this case I am confused. We can reduce And (and OR) language to $M$, we can do exactly the same thing as 1. Where Am I wrong ?
    • – Haskell Fun Aug 13 '17 at 17:37
  • Not sure I understand you, but if I do, then in the first you are right, you can do the reduction in such a way, that you simply solve it in a mentioned way and then create a simple instance, that is or is not in the language based on the result of that computation. But not with NP. You CAN'T check whether individual words are in the language, because there is no polynomial algorithm known to do that. So you probably gonna have to take some NP-complete problem here and find a way to reduce this "multi-instance" word to a corresponding single instance. And that is already quite difficult. – TStancek Aug 13 '17 at 19:02
  • I can't see why you tell about NP-complete. What can it help ? – Haskell Fun Aug 13 '17 at 19:37
  • Well, I see your point probably, you are right, it does not help. That complicates the matter even more. However, you can't go the way of checking individual words either. The last one I do not know how to prove. – TStancek Aug 13 '17 at 19:58
  • Ok, so we solved (a) and (b), yeah ? – Haskell Fun Aug 13 '17 at 20:11
  • I think so, but just in case, can you shortly sum up those solutions? – TStancek Aug 13 '17 at 20:20
  • I edited and added my doubts about (a). Can you explain it ? – Haskell Fun Aug 13 '17 at 21:20
  • Well, this would probably required real-time session, and with someone who has a better grasp of this. Like I said, I am out of this field for a few years now and might have forgotten some things one must not omit. Sorry. But I will try in foreseeable future to edit my answer based on our conversation to better explain my thoughts on this problem, but I recommend on your part to look for some examples of reduction and some exercise in reduction to get what is that whole thing about. – TStancek Aug 14 '17 at 07:11