163:. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit.
147:) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of
474:
296:
are the same, i.e. nondeterministic logarithmic space computation with advice can be made unambiguous. This may be proved using an
496:
159:. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of
444:
358:
20:
268:
function is computable with an advice of length 2 and advice of more than exponential length is not meaningful.
170:
is sometimes defined as the class of decision problems solvable by polynomial size
Boolean circuits, or by
471:
234:
396:
171:
260:. If we are allowed an advice of length 2, we can use it to encode whether each input of length
391:
348:
454:
413:
368:
8:
323:
191:
429:
155:) as the advice, the machine will correctly decide the problem on all inputs of length
440:
354:
160:
450:
409:
401:
364:
186:
40:
36:
478:
436:
297:
247:
195:
128:
194:
problems, such as the unary version of every undecidable problem, including the
278:
28:
405:
382:
Reinhardt, Klaus; Allender, Eric (2000). "Making nondeterminism unambiguous".
490:
467:
344:
16:
Computational input that relies on the length but not content of the input
229:
Advice classes can be defined for other resource bounds instead of
435:. Texts in Theoretical Computer Science. An EATCS Series. Berlin:
135:. One direction of the equivalence is easy to see. If, for every
123:
is equal to the class of decision problems such that, for every
273:
103:
211:
199:
237:
polynomial time Turing machine with an advice of length
131:
correctly deciding the problem on all inputs of length
101:
The most common complexity class involving advice is
426:
428:
427:Hemaspaandra, Lane A.; Ogihara, Mitsunori (2002).
381:
488:
322:, then the polynomial time hierarchy collapses (
264:is contained in the language. Therefore, any
139:, there is a polynomial size Boolean circuit
54:if there is a polynomial time Turing machine
35:of the input, but not on the input itself. A
353:, Cambridge University Press, p. 113,
350:Computational Complexity: A Modern Approach
190:(Adleman's theorem). It also contains some
86:correctly decides the problem on the input
343:
198:. Because of that, it is not contained in
395:
31:that is allowed to depend on the length
489:
58:with the following property: for any
281:with a polynomial amount of advice.
13:
14:
508:
127:, there exists a polynomial size
497:Computational complexity theory
431:The complexity theory companion
21:computational complexity theory
461:
420:
375:
337:
1:
330:
245:) gives the complexity class
166:Because of this equivalence,
62:, there is an advice string
7:
172:polynomial-size non-uniform
115:) can be any polynomial in
74:) such that, for any input
10:
513:
406:10.1137/S0097539798339041
233:. For example, taking a
284:Known results include:
27:is an extra input to a
347:; Barak, Boaz (2009),
279:deterministic logspace
271:Similarly, the class
107:where advice length
324:Karp-Lipton theorem
477:2019-08-05 at the
277:can be defined as
174:Boolean circuits.
303:It is known that
235:non-deterministic
504:
481:
472:A Little Theorem
465:
459:
458:
434:
424:
418:
417:
399:
390:(4): 1118–1131.
379:
373:
371:
341:
318:is contained in
307:is contained in
41:complexity class
37:decision problem
512:
511:
507:
506:
505:
503:
502:
501:
487:
486:
485:
484:
479:Wayback Machine
466:
462:
447:
437:Springer-Verlag
425:
421:
380:
376:
361:
342:
338:
333:
298:isolation lemma
196:halting problem
129:Boolean circuit
17:
12:
11:
5:
510:
500:
499:
483:
482:
460:
445:
419:
397:10.1.1.55.3203
384:SIAM J. Comput
374:
359:
345:Arora, Sanjeev
335:
334:
332:
329:
328:
327:
312:
301:
180:contains both
161:Cook's theorem
82:, the machine
29:Turing machine
15:
9:
6:
4:
3:
2:
509:
498:
495:
494:
492:
480:
476:
473:
469:
468:Lance Fortnow
464:
456:
452:
448:
446:3-540-67419-5
442:
438:
433:
432:
423:
415:
411:
407:
403:
398:
393:
389:
385:
378:
370:
366:
362:
360:9780521424264
356:
352:
351:
346:
340:
336:
325:
321:
317:
313:
310:
306:
302:
299:
295:
291:
287:
286:
285:
282:
280:
276:
275:
269:
267:
263:
259:
257:
253:
249:
244:
240:
236:
232:
227:
225:
221:
217:
213:
209:
205:
201:
197:
193:
189:
188:
183:
179:
175:
173:
169:
164:
162:
158:
154:
150:
146:
142:
138:
134:
130:
126:
122:
118:
114:
110:
106:
105:
99:
97:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
51:
47:
42:
38:
34:
30:
26:
25:advice string
22:
463:
430:
422:
387:
383:
377:
349:
339:
319:
315:
308:
304:
293:
289:
288:The classes
283:
272:
270:
265:
261:
255:
251:
246:
242:
238:
230:
228:
223:
219:
215:
207:
203:
185:
181:
177:
176:
167:
165:
156:
152:
148:
144:
140:
136:
132:
124:
120:
116:
112:
108:
102:
100:
95:
91:
87:
83:
79:
75:
71:
67:
63:
59:
55:
49:
45:
43:
32:
24:
18:
222:)) for any
192:undecidable
455:0993.68042
414:0947.68063
369:1193.68112
331:References
78:of length
66:of length
39:is in the
392:CiteSeerX
309:NEXP/poly
491:Category
475:Archived
90:, given
294:UL/poly
290:NL/poly
266:boolean
453:
443:
412:
394:
367:
357:
320:P/poly
305:coNEXP
274:L/poly
210:)) or
178:P/poly
168:P/poly
121:P/poly
104:P/poly
212:NTIME
200:DTIME
23:, an
441:ISBN
355:ISBN
292:and
184:and
94:and
451:Zbl
410:Zbl
402:doi
365:Zbl
314:If
187:BPP
19:In
493::
470:,
449:.
439:.
408:.
400:.
388:29
386:.
363:,
326:).
316:NP
248:NP
226:.
119:.
98:.
44:P/
457:.
416:.
404::
372:.
311:.
300:.
262:n
258:)
256:n
254:(
252:f
250:/
243:n
241:(
239:f
231:P
224:f
220:n
218:(
216:f
214:(
208:n
206:(
204:f
202:(
182:P
157:n
153:n
151:(
149:A
145:n
143:(
141:A
137:n
133:n
125:n
117:n
113:n
111:(
109:f
96:A
92:x
88:x
84:M
80:n
76:x
72:n
70:(
68:f
64:A
60:n
56:M
52:)
50:n
48:(
46:f
33:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.