Hardness of Approximation in PSPACE and Separation Results for Pebble Games
(2015) 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2015-December. p.466-485- Abstract
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the... (More)
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond - Tompa and Raz - McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.
(Less)
- author
- Chan, Siu Man ; Lauria, Massimo ; Nordstrom, Jakob LU and Vinyals, Marc
- publishing date
- 2015-12-11
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Dymond-Tompa game, pebbling, PSPACE-complete, PSPACE-hardness of approximation, Raz-Mc Kenzie game, resolution depth, reversible pebbling, separation
- host publication
- Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
- series title
- Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
- volume
- 2015-December
- article number
- 7354410
- pages
- 20 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
- conference location
- Berkeley, United States
- conference dates
- 2015-10-17 - 2015-10-20
- external identifiers
-
- scopus:84960371365
- ISSN
- 0272-5428
- ISBN
- 9781467381918
- DOI
- 10.1109/FOCS.2015.36
- language
- English
- LU publication?
- no
- id
- 4457748e-1e0c-440b-8904-34772fe4ac75
- date added to LUP
- 2020-12-18 22:22:42
- date last changed
- 2022-04-19 02:56:19
@inproceedings{4457748e-1e0c-440b-8904-34772fe4ac75,
abstract = {{<p>We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of how hard it is to decide exactly or approximately the number of pebbles needed for a given DAG in these games. We prove that the problem of deciding whether s pebbles suffice to reversibly pebble a DAG G is PSPACE-complete, as was previously shown for the standard pebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graph product constructions we then strengthen these results to establish that both standard and reversible pebbling space are PSPACE-hard to approximate to within any additive constant. To the best of our knowledge, these are the first hardness of approximation results for pebble games in an unrestricted setting (even for polynomial time). Also, since [Chan '13] proved that reversible pebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz and McKenzie '99], our results apply to the Dymond - Tompa and Raz - McKenzie games as well, and from the same paper it follows that resolution depth is PSPACE-hard to determine up to any additive constant. We also obtain a multiplicative logarithmic separation between reversible and standard pebbling space. This improves on the additive logarithmic separation previously known and could plausibly be tight, although we are not able to prove this. We leave as an interesting open problem whether our additive hardness of approximation result could be strengthened to a multiplicative bound if the computational resources are decreased from polynomial space to the more common setting of polynomial time.</p>}},
author = {{Chan, Siu Man and Lauria, Massimo and Nordstrom, Jakob and Vinyals, Marc}},
booktitle = {{Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015}},
isbn = {{9781467381918}},
issn = {{0272-5428}},
keywords = {{Dymond-Tompa game; pebbling; PSPACE-complete; PSPACE-hardness of approximation; Raz-Mc Kenzie game; resolution depth; reversible pebbling; separation}},
language = {{eng}},
month = {{12}},
pages = {{466--485}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
series = {{Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS}},
title = {{Hardness of Approximation in PSPACE and Separation Results for Pebble Games}},
url = {{http://dx.doi.org/10.1109/FOCS.2015.36}},
doi = {{10.1109/FOCS.2015.36}},
volume = {{2015-December}},
year = {{2015}},
}