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