English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 orapproximately the number of pebbles needed for a given DAG in these games. Weprove that the problem of eciding whether $s$~pebbles suffice to reversiblypebble a DAG $G$ is PSPACE-complete, as was previously shown for the standardpebble game in [Gilbert, Lengauer and Tarjan '80]. Via two different graphproduct constructions we then strengthen these results to establish that bothstandard and reversible pebbling space are PSPACE-hard to approximate to withinany additive constant. To the best of our knowledge, these are the firsthardness of approximation results for pebble games in an unrestricted setting(even for polynomial time). Also, since [Chan '13] proved that reversiblepebbling is equivalent to the games in [Dymond and Tompa '85] and [Raz andMcKenzie '99], our results apply to the Dymond--Tompa and Raz--McKenzie gamesas well, and from the same paper it follows that resolution depth isPSPACE-hard to determine up to any additive constant. We also obtain amultiplicative logarithmic separation between reversible and standard pebblingspace. This improves on the additive logarithmic separation previously knownand could plausibly be tight, although we are not able to prove this. We leaveas an interesting open problem whether our additive hardness of approximationresult could be strengthened to a multiplicative bound if the computationalresources are decreased from polynomial space to the more common setting ofpolynomial time.

Hardness of Approximation in PSPACE and Separation Results for Pebble Games