David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
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 Ω(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. © 1988.
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Yi Zhou, Parikshit Ram, et al.
ICLR 2023
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Sankar Basu
Journal of the Franklin Institute