256:
under logarithmic space many-one reductions has led
Ferrarotti et al. to define a different notion of completeness for this class, involving transformations from parameterized problems to polylog-space machines that solve the problems for specific parameter values.
394:
413:
321:
Ferrarotti, Flavio; González, Senén; Schewe, Klaus-Dieter; Torres, José Maria Turull (2022), "Uniform polylogarithmic space completeness",
387:
286:
20:
380:
360:
36:
418:
154:
274:
90:
146:
282:
143:
330:
139:
40:
32:
28:
44:
364:
301:
80:
74:
66:
407:
306:
335:
53:
126:, or if neither is contained in the other. One proof that
368:
47:function in the size of the input. In other words,
249:) and hence violates the space hierarchy theorem.
94:. However, the only proven relationship between
157:. The space hierarchy theorem guarantees that
388:
189:) for some integer k > 0. Suppose problem
8:
316:
314:
395:
381:
334:
213:is complete implies the following O(log
266:
16:Complexity class of decision problems
7:
348:
346:
414:Theoretical computer science stubs
252:The lack of complete problems for
229:in logarithmic space, then decide
14:
177:had a complete problem, call it
173:) for all integers d > 0. If
281:, Addison-Wesley, p. 405,
21:computational complexity theory
1:
323:Frontiers in Computer Science
367:. You can help Knowledge by
361:theoretical computer science
181:, it would be an element of
65:denotes the input size, and
37:deterministic Turing machine
237:) space. This implies that
435:
345:
275:Papadimitriou, Christos H.
336:10.3389/FCOMP.2022.845990
279:Computational Complexity
69:(1) denotes a constant.
35:that can be solved on a
209:). The assumption that
155:space hierarchy theorem
363:–related article is a
217:) space algorithm for
39:by an algorithm whose
153:does not due to the
147:many-one reductions
110:; it is unknown if
419:Complexity classes
376:
375:
241:is an element of
193:is an element of
144:logarithmic space
33:decision problems
426:
397:
390:
383:
352:P ≟ NP
347:
340:
339:
338:
318:
309:
298:
292:
291:
271:
140:complete problem
43:is bounded by a
41:space complexity
29:complexity class
434:
433:
429:
428:
427:
425:
424:
423:
404:
403:
402:
401:
354:
344:
343:
320:
319:
312:
299:
295:
289:
273:
272:
268:
263:
45:polylogarithmic
17:
12:
11:
5:
432:
430:
422:
421:
416:
406:
405:
400:
399:
392:
385:
377:
374:
373:
356:
350:
342:
341:
310:
302:Complexity Zoo
293:
287:
265:
264:
262:
259:
15:
13:
10:
9:
6:
4:
3:
2:
431:
420:
417:
415:
412:
411:
409:
398:
393:
391:
386:
384:
379:
378:
372:
370:
366:
362:
357:
353:
349:
337:
332:
328:
324:
317:
315:
311:
308:
304:
303:
297:
294:
290:
288:9780201530827
284:
280:
276:
270:
267:
260:
258:
255:
250:
248:
244:
240:
236:
232:
228:
224:
220:
216:
212:
208:
204:
200:
196:
192:
188:
184:
180:
176:
172:
168:
164:
160:
156:
152:
148:
145:
141:
137:
133:
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
92:
87:
83:
82:
77:
76:
70:
68:
64:
60:
56:
55:
51: =
50:
46:
42:
38:
34:
30:
26:
22:
369:expanding it
358:
351:
326:
322:
300:
296:
278:
269:
253:
251:
246:
242:
238:
234:
230:
226:
222:
218:
214:
210:
206:
202:
198:
194:
190:
186:
182:
178:
174:
170:
166:
162:
158:
150:
135:
131:
127:
123:
119:
115:
111:
107:
103:
99:
95:
89:
85:
79:
73:
71:
62:
58:
52:
48:
24:
18:
57:((log
408:Categories
329:: 845990,
261:References
61:)), where
233:in O(log
221:: reduce
277:(1994),
134:is that
102:is that
72:Just as
27:is the
355:
285:
243:DSPACE
203:DSPACE
195:DSPACE
183:DSPACE
167:DSPACE
159:DSPACE
142:under
138:has a
54:DSPACE
359:This
307:polyL
254:polyL
245:(log
205:(log
197:(log
185:(log
175:polyL
169:(log
161:(log
151:polyL
128:polyL
124:polyL
118:, if
112:polyL
104:polyL
96:polyL
86:polyL
49:polyL
25:polyL
365:stub
283:ISBN
201:) \
165:) ⊊
149:but
98:and
331:doi
225:to
31:of
19:In
410::
325:,
313:^
305::
130:≠
122:⊊
114:⊊
106:≠
91:QP
88:⊆
84:,
78:⊆
23:,
396:e
389:t
382:v
371:.
333::
327:4
247:n
239:B
235:n
231:A
227:A
223:B
219:B
215:n
211:A
207:n
199:n
191:B
187:n
179:A
171:n
163:n
136:P
132:P
120:P
116:P
108:P
100:P
81:P
75:L
67:O
63:n
59:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.