284:, p. 51). The log-space reduction from any language in NL to STCON proceeds as follows: Consider the non-deterministic log-space Turing machine M that accepts a language in NL. Since there is only logarithmic space on the work tape, all possible states of the Turing machine (where a state is the state of the internal finite state machine, the position of the head and the contents of the work tape) are polynomially many. Map all possible states of the deterministic log-space machine to vertices of a graph, and put an edge between u and v if the state v can be reached from u within one step of the non-deterministic machine. Now the problem of whether the machine accepts is the same as the problem of whether there exists a path from the start state to the accepting state.
238:. The st-connectivity problem can be shown to be in NL, as a non-deterministic Turing machine can guess the next node of the path, while the only information which has to be stored is the total length of the path and which node is currently under consideration. The algorithm terminates if either the target node
107:
63:
114:
226:. The interest in this problem in computational complexity concerns its complexity with respect to more limited forms of computation. For instance, the
258:
100:
378:
355:
231:
406:
78:
396:
33:
325:, so Reingold's work showed that SL is the same class as L. On alternating graphs, the problem is
318:
401:
368:
38:
277:
88:
287:
223:
8:
273:
48:
219:
68:
24:
374:
351:
83:
302:
227:
140:
128:
73:
322:
235:
321:. Undirected st-connectivity was previously known to be complete for the class
343:
326:
310:
152:
272:, that is, every problem in the class NL is reducible to connectivity under a
390:
364:
314:
160:
269:
215:
43:
53:
214:
On a sequential computer, st-connectivity can easily be solved in
257:, is also in the class NL, since NL = coNL by the
242:
is reached, or the length of the path so far exceeds
234:
using only a logarithmic amount of memory is called
290:guarantees that the algorithm can be simulated in
388:
276:. This remains true for the stronger case of
108:
195:is a directed graph with a path from vertex
170:Formally, the decision problem is given by
115:
101:
348:Introduction to the Theory of Computation
363:
330:
281:
389:
342:
246:, the number of nodes in the graph.
230:of problems that can be solved by a
13:
317:. This research won him the 2005
14:
418:
232:non-deterministic Turing machine
350:, Thompson Course Technology,
264:In particular, the problem of
1:
373:, New York: Springer-Verlag,
336:
259:Immerman–Szelepcsényi theorem
209:
79:Strongly connected component
7:
307:undirected s-t connectivity
10:
423:
64:K-connectivity certificate
319:Grace Murray Hopper Award
298:) deterministic space.
309:and was shown to be in
370:Descriptive Complexity
278:first-order reductions
39:Algebraic connectivity
301:The same problem for
143:asking, for vertices
407:NL-complete problems
224:breadth-first search
274:log-space reduction
255:st-non-connectivity
49:Rank (graph theory)
397:Graph connectivity
249:The complement of
220:depth-first search
69:Pixel connectivity
25:Graph connectivity
19:Relevant topics on
303:undirected graphs
288:Savitch's theorem
125:
124:
84:Biconnected graph
414:
383:
360:
228:complexity class
204:
190:
141:decision problem
129:computer science
117:
110:
103:
74:Vertex separator
16:
15:
422:
421:
417:
416:
415:
413:
412:
411:
402:Directed graphs
387:
386:
381:
358:
344:Sipser, Michael
339:
333:, p. 54).
266:st-connectivity
251:st-connectivity
212:
176:
174:
133:st-connectivity
121:
59:St-connectivity
12:
11:
5:
420:
410:
409:
404:
399:
385:
384:
379:
365:Immerman, Neil
361:
356:
338:
335:
211:
208:
207:
206:
153:directed graph
123:
122:
120:
119:
112:
105:
97:
94:
93:
92:
91:
86:
81:
76:
71:
66:
61:
56:
51:
46:
41:
36:
28:
27:
21:
20:
9:
6:
4:
3:
2:
419:
408:
405:
403:
400:
398:
395:
394:
392:
382:
380:0-387-98600-6
376:
372:
371:
366:
362:
359:
357:0-534-95097-3
353:
349:
345:
341:
340:
334:
332:
331:Immerman 1999
328:
324:
320:
316:
315:Omer Reingold
312:
308:
304:
299:
297:
293:
289:
285:
283:
282:Immerman 1999
279:
275:
271:
267:
262:
260:
256:
252:
247:
245:
241:
237:
233:
229:
225:
221:
217:
202:
198:
194:
188:
184:
180:
173:
172:
171:
168:
166:
162:
158:
154:
150:
146:
142:
138:
134:
130:
118:
113:
111:
106:
104:
99:
98:
96:
95:
90:
87:
85:
82:
80:
77:
75:
72:
70:
67:
65:
62:
60:
57:
55:
52:
50:
47:
45:
42:
40:
37:
35:
32:
31:
30:
29:
26:
23:
22:
18:
17:
369:
347:
306:
300:
295:
291:
286:
268:is actually
265:
263:
254:
250:
248:
243:
239:
213:
200:
196:
192:
186:
182:
178:
169:
164:
156:
148:
144:
136:
132:
126:
58:
34:Connectivity
329:-complete (
270:NL-complete
253:, known as
216:linear time
391:Categories
337:References
305:is called
294:(log
218:by either
210:Complexity
44:Cycle rank
161:reachable
54:SPQR tree
367:(1999),
346:(2006),
189:⟩
177:⟨
175:PATH = {
185:,
181:,
377:
354:
89:Bridge
163:from
155:, if
151:in a
139:is a
137:STCON
375:ISBN
352:ISBN
147:and
313:by
222:or
199:to
159:is
135:or
127:In
393::
323:SL
261:.
236:NL
191:|
167:.
131:,
327:P
311:L
296:n
292:O
280:(
244:n
240:t
205:.
203:}
201:t
197:s
193:D
187:t
183:s
179:D
165:s
157:t
149:t
145:s
116:e
109:t
102:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.