Bezpośrednia redukcja z

14

Wiemy, że jest w według twierdzenia Immermana – Szelepcsényiego, a ponieważ jest dlatego to wiele-jeden obszar dziennika, który można zredukować do . Ale czy istnieje bezpośrednia / kombinatoryczna redukcja, która nie przechodzi przez wykres konfiguracji maszyn Turinga w ?st-non-connectivityNLst-connectivityNL-hardst-non-connectivityst-connectivityNL

stConnectivity (a.k.a. stPATH):

Given directed graph G and vertices s and t,

Is there a directed path from vertex s to vertex t?


Clarifications:

You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)

It is possible to unpack the proof of NL-hardness of st-connectivity and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is not this, I want a conceptually direct reduction. Let me give an analogy with the NP case. We can reduce various NP-complete problems to each other by using the fact that they are in NP therefore reduce to SAT and SAT reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce HamPath or VertexCover or 3-Coloring to SAT we don't say HamPath is in NP and therefore reduces to SA since SAT is NP-hard. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path. Another example, we have reductions from other problems in NL to st-Connectivity which do not rely on NL-completeness of st-Connectivity, e.g. Cycle, StronglyConnected, etc, they involve modification on the input graph (and do not refer to any Turing machines that is solving them).

I still don't see any reason why this cannot be done for this one. I am looking for a reduction of this kind.

It might be the case that this is not possible and any reduction would conceptually go through the NL-hardness result. However I don't see why that should be the case, why the situation would be different from the NP case. Obviously to give a negative answer to my question we would need to be more formal about when does a proof conceptually include another proof (which is proof theory question that AFAIK not settle in a satisfactory way). However note that for a positive answer one does not need such a formal definition and I am hoping that is the case. (I will think about how to formalize what I am asking in a faithful way when I find more free time. Essentially I want a reduction that would work even if we didn't know that the problem is complete for NL.)

Using the proof of Immerman–Szelepcsényi theorem is fine, using NL-completeness of stPATH and configuration graph of an NL machine is what I want to avoid.

Kaveh
źródło
@Raphael, I like to use a different font for the names of mathematical concepts like complexity classes as is the common practice in the literature. Please don't remove them.
Kaveh
1
Sorry, but that looks horrible. If you must, use a different font, but then please be consistent: you mix mathsf with standard math font, and even use different fonts in one word!
Raphael
@Raphael, I am using them in a consistent way. Mathsf is used for distinguishing complexity classes. I will think about moving "complete" and "hard" outside into text part (the problem with that is it would make them typed using different fonts.)
Kaveh
"Consistent" is not equal to "typographically pleasing". (Furthermore, the distinction is not really needed here, especially not the one between complexity classes and problems (which, adding to the pain, look awful in raw math font)).
Raphael
@Raphael, sure, I didn't claim so. You objected to "inconsistency" of the way I use them, I just wanted to point out that is not the case. My style is to distinguish names of mathematical concept like P from the rest of math/text and I would like to do it in a consistent way. Anyway, I will think about how to make it typographically nicer while preserving the style.
Kaveh

Odpowiedzi:

4

It is possible, if messy, to convert the proof of the Immerman-Szelepcsényi theorem to the reduction you want. There is absolutely no need to use the NL-completeness of st-connectivity.

Given an instance G=(V,E),s,t, we construct a new graph G=(V,E),s,t. The "major vertices" of V record the following information: the current distance d from s, the number of vertices of distance at most d1, the number of vertices of distance d1 counted so far, the current vertex we're guessing if it has distance at most d1, the number of vertices of distance at most d counted so far, the current vertex we're determining whether it has distance at most d. The minor vertices handle the part where we guess a path of length at most d1 to a vertex which we guess to be of distance at most d1. Edges that involve showing the vertex t is reachable from s are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance d to distance d+1, we copy the requisite information. The starting vertex s accounts for the fact that s is the only vertex of distance zero. The ending vertex t is pointed at by all vertices representing the fact that the process has finished up to (and including) distance n1, where n=|V|.

As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.

Yuval Filmus
źródło