White pebbles help. (English) Zbl 0657.68049

Author’s summary: “It is proved that for infinitely many n there is a directed acyclic graph with vertex indegrees bounded by 2 that has a strategy of the black-white pebble game using n pebbles and for which any strategy of the black pebble game requires \(\Omega\) (n log n/log log n) pebbles. This shows that there is a family of straight-line programs for which nondeterminism reduces the space required to evaluate the programs by more than any constant factor.”
Reviewer: R.Klette


68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)
68Q45 Formal languages and automata
Full Text: DOI


[1] Cook, S.A., An observation on time-storage trade-off, J. comput. system sci., 9, 308-316, (1974) · Zbl 0306.68026
[2] Cook, S.A.; Sethi, R., Storage requirements for deterministic polynomial finite recognizable languages, J. comput. system sci., 13, 25-37, (1976) · Zbl 0337.68031
[3] Friedman, H., Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, (), 361-389
[4] Hewitt, C.E.; Paterson, M.S., Comparative schematology, (), 119-127 · Zbl 0401.68002
[5] Klawe, M.M., A tight bound for black and white pebbles on the pyramid, J. assoc. comput. Mach., 32, No. 1, 218-228, (1985) · Zbl 0632.68042
[6] Lengauer, T.; Tarjan, R., The space complexity of pebble games on trees, Inform. process. lett., 10, 184-188, (1980) · Zbl 0449.68028
[7] Lengauer, T.; Tarjan, R., Asymptotically tight bounds on time-space trade-offs in a pebble game, J. assoc. comput. Mach., 29, No. 4, 1087-1130, (1982) · Zbl 0495.68037
[8] Loui, M.C., The space complexity of two pebble games on trees, ()
[9] Meyer auf der Heide, F., A comparison of two variations of a pebble game on graphs, Theoret. comput. sci., 13, 315-322, (1981) · Zbl 0454.05031
[10] Pippenger, N., Pebbling, IBM research report RC 8258, (1980)
[11] Pippenger, N., Advances in pebbling, (), 407-417
[12] Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1970) · Zbl 0188.33502
[13] Wilber, R.E., A comparison of the black and black-white pebble games, ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.