Hardness of Approximation in PSPACE and

Separation Results for Pebble Games

]Siu Man Chan

Massimo Lauria
Sapienza — Università di Roma, Italy
Jakob Nordström
University of Copenhagen, Denmark, and Lund University, Sweden
Marc Vinyals
University of Auckland, New Zealand

Hardness of Approximation in PSPACE and

Separation Results for Pebble Games
This is the full-length version of the paper with the same
title that appeared in
Proceedings of the 56th IEEE Symposium on Foundations of
Computer Science (FOCS '15).

[CE]HARDNESS OF APPROXIMATION IN PSPACE AND SEPARATION FOR PEBBLE GAMES

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 -complete, as was previously
shown for the pebble game in [Gilbert, Lengauer and Tarjan '80].
Via two different graph product constructions we then strengthen
these results to establish that both and reversible
pebbling space are -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 -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.

§ INTRODUCTION

In the pebble game first studied by Paterson and
Hewitt [27], one starts with an empty directed
acyclic graph (DAG) $G$ with bounded fan-in (and which in this paper
in addition will always have a single sink) and places pebbles on the
vertices according to the following rules:

If all (immediate) predecessors of an empty vertex $v$ contain
pebbles, a pebble may be placed on $v$.

A pebble may be removed from any vertex at any time.

The goal is to get a pebble on the sink vertex of $G$ with all other
vertices being empty, and to do so while minimizing the total number
of pebbles on $G$ at any given time (the
pebbling price
of $G$).
This game models computations with execution
independent of the actual

input. A pebble
on a vertex indicates that the corresponding value is currently kept
in memory and the objective is to perform the computation with the
minimum amount of memory.

The pebble game has been used to study
flowcharts and recursive schemata [27],
register allocation [33],
time and space as Turing-machine
resources [9, 19],
and algorithmic time-space trade-offs
[6, 35, 36, 37, 38].
In the last 10–15 years, there has been a renewed interest in pebbling in
the context of proof complexity as discussed in the
survey [25]
(although in this context one is often interested also in the slightly
more general black-white pebble game introduced
in [11]), and pebbling has also turned out to be useful for
applications in cryptography [13, 1].
An excellent overview of pebbling up to ca. 1980 is given
in [28] and some more recent developments are
covered in the upcoming survey [26].

Bennett [3] introduced the
reversible pebble game as part of a broader
program [2] to investigate
possibilities to eliminate (or significantly reduce) energy
dissipation in logical computation.  Another reason reversible
computation is of interest is that observation-free quantum
computation is inherently reversible.  In the reversible pebble game,
the moves performed in reverse order should also constitute a legal
pebbling, which means that the rules for pebble placement and removal
become symmetric as follows:

* If all predecessors of an

empty vertex $v$   contain pebbles,
a pebble may  be placed on $v$.

* If all predecessors of a pebbled vertex $v$

contain pebbles,
the pebble on $v$ may be removed.

Reversible pebblings
of DAGs
have been studied in
[24, 20]
and have been employed to shed light on
time-space trade-offs in
reversible simulation of irreversible computation in
[23, 22, 41, 4].
In a different line of work
Potechin [29]
implicitly used the reversible pebble game for proving lower bounds on monotone
space complexity, with the connection made
explicit in the follow-up works [10, 16].

Another pebble game on DAGs that will be of interest in this paper is the
[14]
played on a DAG $G$ by a

and a

This game is played in rounds, with both players starting at the sink
in the first round.
In the following rounds, places a pebble on some vertex
of $G$ after which
either stays at the current vertex or moves to the newly
pebbled vertex. This repeats until at the end of a round is standing on a vertex with all (immediate) predecessors pebbled (or
on a source, in which case the condition vacuously holds),
at which point the game ends.
Intuitively, is challenging to “catch me if
you can” and wants to play for as many rounds as possible, whereas
wants to “surround” as quickly as possible.

of $G$
is the smallest number $\dtnrounds$
such that can always finish the game in at
most $\dtnrounds$ rounds.

The has been used to establish that for parallel time a
speed-up by a logarithmic factor is always possible [14],
and  in [39] it was shown that

a slightly modified variant of this game exactly characterizes
parallelism in complexity classes like $\complclassformat{AC}^i$,
$\NC$, and $\Pclass$,
and can be used to re-derive, for instance, Savitch's theorem.
Furthermore, collapses or separations of these classes can in
principle be recast (or discovered) as bounds on .
Interestingly, this characterization of parallelism
extends to proof complexity as well as discussed
in [7].

A final game with pebbles that we want to just mention
without going into any details
is the
introduced in [31]
to study the depth complexity of decision
trees solving search problems.

The reason for bringing up the
and s is that it was shown
in [7]
that both games are actually equivalent to the reversible
pebble game. Hence, any bounds derived for the reversible pebble
game also hold for
and .

The main focus of this paper is to study how hard it is to decide
exactly or approximately the pebbling
price of a DAG. For the pebble game
Gilbert  [17]

showed that given a DAG $G$ and a positive integer $\pebsp$ it is
-complete to determine whether space $\pebsp$
is sufficient to pebble $G$ or not.

It would seem natural to suspect that reversible pebbling price should
be -complete as well, but the construction
in [17] cannot be used to show this.

Given that pebbling price is hard to determine exactly, an even more
interesting question is if anything can be said regarding the hardness
of approximating pebbling price. Although this seems like a very
natural and appealing question, apparently next to nothing has been
known about this.

Wu  [40]
showed that “one-shot” pebbling price is hard to
approximate to within any multiplicative constant assuming the
Small Set Expansion (SSE) hypothesis.
In a one-shot pebbling one is only allowed to pebble each vertex once,
however, and this is a major restriction since the complexity now drops
from -complete to

Note that containment in is easy to see since any one-shot
pebbling can be described concisely just by listing the order in which
the vertices should be pebbled (and it is easy to compute when a pebble is
no longer needed and can be removed). In contrast, in the general case
pebbling strategies that are optimal with respect to space

can sometimes provably
require exponential time.

One can also go in the other direction and study more general pebble
games, such as the AND/OR pebble game introduced by
Lingas [21] in one of the works leading up
to [17].

Here every vertex is labelled AND or OR. For AND-vertices we have
the usual pebbling rule, but for
OR-vertices it is sufficient to just have one pebble on some
predecessor in order to be allowed to pebble the vertex.
This game has a relatively straightforward reduction from hitting
set [15], which shows that it is hard to
approximate to within a logarithmic factor, but the reduction
crucially depends on the OR-nodes.

We remark that hardness of approximation in for other problems
has been studied in [5], but those
techniques seem hard to adapt to pebble games since the reduction from
QBF to pebbling is inherently unable to preserve gaps.

Another problem that we study
in the current paper
is the relation between pebbling price and reversible pebbling price.  Clearly, the space
needed to reversibly pebble a graph is at least the space required in the
pebble game. It is also not hard to see that there are
graphs that require strictly more pebbles in a reversible setting: for
a directed path on $n$ vertices only $2$ pebbles are needed in the
game, while it is relatively straightforward to show that
the reversible pebbling space is
$\bigtheta{\log n}$ [3, 24].
However, for “classic” graphs studied in the pebbling literature,
such as binary trees, pyramids, certain superconcentrators, and the
worst-case graphs in [30],

the reversible and pebbling prices coincide asymptotically,
and are sometimes markedly closer than an additive logarithm apart.

This raises the question whether reversible and pebbling
can be asymptotically separated with respect to space.  It might be
worth pointing out in this context that for Turing machines
it was proven in [22] that any computation can be
simulated reversibly in exactly the same space.
In the more restricted pebbling model,  it was shown
in [20]
that if the pebbling price of a DAG $G$ on $n$ vertices
is $\pebsp$, then $G$ can be reversibly pebbled with at most
$\pebsp^2 \log n$ pebbles.

Thus, if there is not only an additive but also a multiplicative
separation between and reversible  pebbling price, such a
separation cannot be too large.

§.§ Our Results

We obtain the following results:

* We establish an asymptotic separation between and
reversible pebbling by exhibiting
families of graphs

$\set{G_n}_{n=1}^{\infty}$ of size $\bigtheta{n}$
with a single sink and fan-in $2$
which have standard pebbling price $\pebsp(n)$
and reversible pebbling price $\bigomega{\pebsp(n) \log n}$.
This construction works for
any $\pebsp(n) = \Bigoh{n^{1/2 - \epsilon}}$
with $\epsilon > 0$ constant,

where the constant hidden in the asymptotic notation in the lower
bound has a (mild)   dependence on $\epsilon$.

We prove that determining reversible pebbling price
is -complete. That is,
given a single-sink DAG $G$ of fan-in $2$ and a parameter $\pebsp$, it
is -complete to decide whether $G$ can be reversibly
pebbled in space $\pebsp$ or not.

* Finally, we present two different graph products
(for and reversible pebbling, respectively)
that take DAGs $G_i$ of size $n_i$
with pebbling price $\pebsp_i$ for $i=1,2$
and yield  a DAG

of size $\Bigoh{(n_1 + n_2)^2}$
with pebbling price
$s_1 + s_2 + \pebshiftconst$
(for $\pebshiftconst = \pm 1$ depending on the flavour of the pebble

Combining these graph products with the -completeness results
for pebbling in [17] and
reversible pebbling in  item:pspace-hardness-result,
we deduce that
for any fixed $\pebsepconst$
the promise problem of deciding for a DAG $G$ (with a single sink
and fan-in $2$) whether it can be pebbled in space $\pebsp$ or
requires space $\pebsp + \pebsepconst$ is -hard in both the
and the reversible pebble game.

We need to provide more formal definitions before going into a
detailed discussion of techniques, but want to stress right away that
a key feature of the above results is the bounded fan-in
condition. This is the standard setting for pebble games in the
literature and is also crucial in most of the applications mentioned
above.  Without this constraint it would be much easier, but also much
less interesting, to prove our
results.[The reason to emphasize this is that for
unbounded fan-in proved a -completeness result
for reversible pebbling in [8], but this
result uses simpler constructions and techniques that do not
transfer to the bounded fan-in setting. Another, somewhat related,

example is that deciding space in the black-white pebble game
has also been shown to be -complete for unbounded indegree
in [18], but there the unbounded
fan-in can be used to eliminate the white pebbles completely,
and again the techniques fail to transfer to the bounded indegree

Another aspect worth pointing out is that although the reversible
pebble game is weaker than the
pebble game, it is technically much more challenging to
analyze. The reason for this is that a pebbling will always
progress in a “forward sweep” through the graph in topological order,
and so one can often assume without loss of generality that once one
has pebbled through some subgraph the pebbling will never touch this
subgraph again.  For a reversible pebbling this is not so,
since any pebble placed on any descendant of vertices in the subgraph
will also have to be removed at some later time, and this has to be
done in reverse topological order. Therefore, in any reversible
pebbling there will be alternating phases of “forward sweeps”  and
“reverse sweeps,” and these phases can also be interleaved at
various levels. For this reason, controlling the progress of a reversible
pebbling is substantially more complicated.

Despite the additional technical

however, we consider the reversible pebble game to be at least as
interesting to study as the and black-white pebble games
in view of its tight connection with parallelism in circuit and proof
complexity as described in [7].

§.§ Follow-up Work

Our hardness of approximation result for the standard pebble game was improved
by Demaine and Liu [12], who proved that it is
$\pspace$-hard to approximate the standard space of a graph of size
$n$ within an additive $n^{1/3-\epsilon}$ term.

§.§ Organization of This Paper

We present the necessary preliminaries in
and then give a detailed overview of our results in
Due to space constraints we can only sketch the proofs
in this extended abstract
and therefore refer to the upcoming full-length version for all
missing details.  Some concluding remarks are presented in

We present the necessary preliminaries in
and then give a detailed overview of our results in
We prove an asymptotic separation between and reversible pebbling in
In sec:tight-bounds we compute the exact price of some classic graphs, trees and pyramids, that we use in sec:technical-constructions to construct technical gadgets. These play a key role in sec:pspace-completeness-reversible, where we show that reversible pebbling is -complete.
We detail the graph product for reversible pebbling in sec:blow-up-reversible and its counterpart for pebbling in sec:blow-up-standard.
Some concluding remarks are presented in

§ PRELIMINARIES

All logarithms in this paper are base $2$ unless otherwise specified.
For a positive integer $n$ we write $\intnfirst{n}$ to  denote the set
of integers $\set{1, 2, \ldots, n}$.
We use Iverson bracket notation

\begin{equation}
\ib{B} =
\begin{cases}
1 & \text{if the Boolean expression $B$ is true;} \\
0 & \text{otherwise;}
\end{cases}
\end{equation}

to convert Boolean values to integer values.

§.§ Boolean Formula Notation and Terminology

A literal
over a Boolean variable $\varx$ is either
the variable $\varx$ itself or
its negation
(a positive or negative literal,
respectively). A clause
$\clc = \lita_1 \lor \formuladots \lor \lita_{\clwidth}$
is a disjunction of literals.
A $\clwidth$-clause is a clause that
contains at most $\clwidth$ literals. A  formula $\fstd$ in
conjunctive normal form (CNF)
is a conjunction of
$\fstd = \clc_1 \land \formuladots \land \clc_m$.
is a CNF formula consisting of
s. We think of clauses and CNF formulas as sets, so that
the order of elements is irrelevant and there are no repetitions.

quantified Boolean formula (QBF)
is a formula

$\QBF = Q_1 x_1 \, Q_2 x_2 \, \ldots \, Q_n x_n \, \, \fstd$,
$\fstd$ is a CNF formula over variables $x_1, \ldots, x_n$
$Q_i \in \set{\forall, \exists}$
are universal or existential quantifiers
the formula is in prenex normal form with all
variables bound by quantifiers).
It was shown in [34] that it is -complete to
decide whether a QBF is true or not
(where we can assume that $\fstd$ is a 3).

§.§ Graph Notation and Terminology

We write
$G = (V,E)$
to denote a graph with vertices $\vertices{G}=V$ and edges
$\edges{G}=E$. All graphs in this paper are directed acyclic graphs
An edge
$(u,v) \in \edges{G}$
is an outgoing edge of $u$ and an
incoming edge of $v$, and we say that $u$ is a
predecessor of $v$ and that $v$ is a
successor of $u$.
We write $\prednode[G]{v}$ to denote the set of all predecessors of $v$
in $G$ and $\succnode[G]{v}$ to denote all its successors.
Vertices with no incoming edges are called sources and
vertices with no outgoing edges are called sinks.
For brevity, we will sometimes refer to a DAG with a unique
sink as a
and this sink will usually be denoted $\sink$.

Taking the transitive closures of the predecessor and successor
relations, we define the
$\ancnode[G]{v}$ of $v$ to be the set of vertices that have a path to $v$
and the
to be the set of vertices on some path from $v$.
By convention, $v$ is an ancestor and descendant of itself.
We write
$\pancnode[G]{v} = \ancnode[G]{v} \setminus \set{v}$
$\pdescnode[G]{v} = \descnode[G]{v} \setminus \set{v}$
to denote the
proper ancestors and
proper descendants of $v$, respectively.
These concepts are extended to sets of pairwise incomparable
vertices by taking unions so that
$\ancnode[G]{U} = \Union_{u \in U} \ancnode[G]{u}$,
$\pancnode[G]{U} = \Union_{u \in U} \pancnode[G]{u}$,
et cetera,
where we say that
the vertices in $U$ are pairwise incomparable when no vertex in the
set is an ancestor of any other vertex in the set.
When the graph $G$ is clear from context we will sometimes drop it
from the notation.

§.§ and Reversible Pebble Games

pebble configuration
on a DAG
$G = (V,E)$
is a subset of vertices
$\pconf \subseteq V$.
We consider the following three rules for manipulating pebble

$\pconfafter=\pconfbefore\unionSP \set{v}$
$v \notin \pconfbefore$
such that
$\prednode[G]{v} \subseteq \pconfbefore$
(a pebble placement on $v$).

$\pconfafter = \pconfbefore\setminus \set{v} $ for
$ v\in \pconfbefore$
(a pebble removal from $v$).

$\pconfafter = \pconfbefore\setminus \set{v} $ for
$ v\in \pconfbefore$
such that
$\prednode[G]{v} \subseteq \pconfbefore$
(a reversible pebble removal from $v$).

to $\pconf_{\stoptime}$
is a   sequence of pebble configurations
\pebbling =
(\pconf_{0}, \pconf_{1}, \ldots, \pconf_{\stoptime})
where each configuration is obtained from the preceding one by the
and <ref>
while in a
reversible pebbling
and <ref>
should be used.
The time of a pebbling
$\pebbling = (\pconf_0, \ldots, \pconf_{\stoptime})$
is $\pebtime{\pebbling} = \stoptime$,
and the space is
$\pebspace{\pebbling} =
\maxofexpr[0 \leq t \leq {\stoptime}]{\setsize{\pconf_t}}$.

We say that a pebbling is

if $\pconf_0 = \emptyset$ and

pebbling price
of a pebble configuration $\pconf$
is the minimum space of any pebbling on $G$  ending
and we define the
reversible pebbling price
by taking the minimum over all reversible pebblings
reaching $\pconf$.

The pebbling price of a
$G$ with sink $\sink$
$\blackprice{G} = \blackprice[G]{\set{\sink}}$,
and the reversible pebbling price of $G$ is
$\persistentprice{G} = \persistentprice[G]{\set{\sink}}$.
We refer to such pebblings as
() pebblings of $G$
pebbling strategies for $G$.

Again, when $G$ is clear from context we can drop it from the
notation, and from now on we will usually abuse notation by omitting
the curly brackets around singleton vertex sets.

For technical reasons, we will often be interested in distinguishing
particular flavours of reversible pebblings.
Suppose that $v$ is a vertex in $G$ and that
$\pebbling = (\pconf_0 = \emptyset, \pconf_1,\ldots, \pconf_{\stoptime})$
is a reversible pebbling. We will use the
following terminology and notation:

* $\pebbling$ is a visiting pebbling of $v$ if
$v \in \pconf_{\stoptime}$.
visiting price
of $v$
is the minimal space of any such pebbling.

* $\pebbling$ is a
surrounding pebbling of $v$ if
$\prednode{v} \subseteq \pconf_{\stoptime}$
and the
surrounding price

is the minimal space of any such pebbling.

* $\pebbling$ is a persistent pebbling of $v$ if
it is a reversible pebbling of $v$ in the sense defined before, such that
We will sometimes refer to
as the
persistent price
of $v$ to distinguish it from the visiting and surrounding prices.

We also define the
visiting price for a  $G$ with sink $\sink$ as
$\visitprice{G}= \visitprice[G]{\sink}$
and the surrounding price as
$\surroundprice{G} = \surroundprice[G]{\sink}$.

Note that because of reversibility we could obtain exactly the same
visiting space measure by defining a visiting pebbling of $v$ to be a
$\pebbling = (\pconf_0, \pconf_1,\ldots, \pconf_{\stoptime})$
such that

$\pconf_0 = \pconf_{\stoptime} = \emptyset$
$v \in \Union_{0\leq t \leq \stoptime} \pconf_t$,
and let the visiting price be the minimal space of any such pebbling.
This is because once we have reached a configuration
containing $v$ we can simply run the pebbling backwards
(because of reversibility) until we reach the empty configuration again.

We can therefore think of a pebbling as visiting $v$ if
there is a pebble on $v$ at some point but this pebble does not stay
on $v$ until the end of the pebbling.
In a persistent pebbling the pebble remains on $v$ until all
other pebbles have been removed.
A surrounding pebbling,
finally, is a pebbling that reaches exactly the point where a pebble
could be placed on $v$, since all its predecessors are covered by
pebbles ($v$ is “surrounded” by pebbles),
but where $v$ is not necessarily pebbled.

It is not hard to see that for a  $G$ we have the

\begin{equation}
\label{eq:standard-leq-visiting}
\blackprice{G} \leq \visitprice{G}
\end{equation}

\begin{equation}
\label{eq:surrounding-leq-visiting-leq-persistent}
\surroundprice{G} \leq \visitprice{G} \leq \persistentprice{G}
\eqperiod
\end{equation}

Perhaps slightly less obviously,
we also have the following useful equality.

For any vertex $v$ in a DAG $G$ it holds that
$\surroundprice{v} = \persistentprice{v} - 1$.

To see that $\persistentprice{v} \leq \surroundprice{v}+1 $
consider a surrounding pebbling $\pebbling^{S}$ of space
Let $\pebbling^{*}     $ be the pebbling which
first runs $\pebbling^{S}$ to surround $v$,
then puts a pebble on $v$, and
finally runs the reverse of $\pebbling^{S}$ to “unsurround” $v$ (while
keeping the pebble on $v$).
Since $\pebbling^{*}$ is a persistent pebbling of space
$\surroundprice{v}+1$, the inequality follows.

We now prove that $\surroundprice{v} \leq \persistentprice{v}-1 $.

Consider a persistent pebbling $\pebbling$ for $v$ of space
Let $\timet$ be the last time that a pebble is put on $v$.
Then vertex $v$ is surrounded at time $\timet$, and
there is a pebble on $v$ since time $\timet$.
Let $\pebbling_{\geq \timet}$
be the pebbling obtained from $\pebbling$

time $\timet$, with the modification that vertex $v$ has no pebble
throughout $\pebbling_{\geq \timet}$,
and let $\pebbling^{R}_{\geq \timet}$ be this pebbling run in reverse.
Then $\pebbling^{R}_{\geq \timet}$
is a surrounding pebbling in space at
most $\persistentprice{v}-1$, and the inequality follows.

§.§ The Dymond–Tompa and Raz–McKenzie Games

As described above, the
on a  $G$
is played in rounds by  two players
and  .
In the first round places a pebble on the sink $\sink$
and challenges this vertex.
In all subsequent rounds, places a pebble on an arbitrary
empty vertex and chooses to either challenge this new
(which we refer to as

or to re-challenge the previously challenged vertex

(referred to as ).
The game ends when at the end of a round all the (immediate)
predecessors of the currently challenged vertex are covered by
pebbles.[We remark that our description
follows [7] and thus

differs slightly from the original definition in [14],

but the two versions are equivalent
for all practical purposes.]

$\dtprice{G}$ of $G$

is the maximal number of pebbles $\dtnrounds$ needed for to
finish the game, or expressed differently the smallest
number $\dtnrounds$ such that has a strategy to make the
game end in at most $\dtnrounds$ rounds regardless of how

Let us also for completeness describe the
Raz–McKenzie game,
which is also played on a  $G$
by  two players
and  .
In the first round places a pebble on the sink $\sink$
and colours it .
In all subsequent rounds, places a pebble on an arbitrary
empty vertex and then colours this new pebble either or .
The game ends when there is a vertex with a pebble, while all
its predecessors in the graph have pebbles.

$\rmprice{G}$ of $G$
is the smallest number $\rmnrounds$
such that has a strategy to make the game end in at
most $\rmnrounds$ rounds regardless of how plays.

The intuition for this game is that the vertices on the graphs have
assigned values true () or false (), with the condition
that each vertex has value equal to the conjunction of the values of
its  predecessors. claims that the sink is false, but the above
condition vacuously implies that all source vertices must be true.

loses when discovers a violation of the condition.
wants to find the violation as soon as possible, while
wants to fool for as long as possible.

In [7]
proved that the equalities

\begin{equation}
\label{eq:chan13-equalities}
\dtprice{G} = \rmprice{G} = \persistentprice{G}
\end{equation}

hold for any  $G$, that the reversible pebbling price, the and the
all coincide.
Thus, any result we prove for one of these games is also
guaranteed to hold for the other games.

The above equalities are very convenient in that they allow us to
switch back and forth between the reversible pebble game and the
(or ) when proving upper and
lower bounds, depending on which
perspective is more suitable at any given time.

In particular, when proving lower bounds for reversible pebblings it

is often helpful
to do so by devising good strategies in the
. One final technical remark in this context is that in all
such strategies that we construct it holds that will
either or to an ancestor of the currently challenged
vertex. Because of this we can assume without loss of generality that
only pebbles vertices in the subgraph consisting of
ancestors of the currently challenged vertex. If pebbles
some vertex outside of this subgraph will just stay put
on the current vertex, and so just wastes a round.

§ OVERVIEW OF RESULTS AND SKETCHES OF PROOFS

In this section we give a detailed overview of our results and also
sketch some of the main ideas in the proofs.

We refer to the upcoming full-length version
for all formal proofs and missing technical details.

In the rest of the paper, we then provide all the missing technical
definitions and present the actual formal proofs.

§.§ Separation Between and Reversible Pebbling

As mentioned in sec:intro, the strongest separation hitherto
known between and reversible pebbling is for the
length-$\pathnvert$ path on
vertices $\set{v_{1}, v_{2},  \ldots, v_{\pathnvert + 1}}$
with edges
$(v_{i}, v_{i+1})$ for all $i \in \intnfirst{\pathnvert}$,
which has a pebbling with $2$ pebbles
whereas reversible pebblings require space
$\bigtheta{\log\ell}$ [3, 24].
We give a simple construction improving this to a multiplicative
logarithmic separation.

For any function $\pebsp(n) = \Bigoh{n^{1/2 - \epsilon}}$
for $\epsilon > 0$ constant there are DAGs
$\set{G_n}_{n=1}^{\infty}$ of size $\bigtheta{n}$
with a single sink and fan-in $2$
such that
$\blackprice{G} = \bigoh{\pebsp(n)}$
$\persistentprice{G} = \bigomega{\pebsp(n) \log n}$
(where the hidden constant depends linearly on $\epsilon$).

A first observation is that if we did not have the bounded fan-in
would be very easy.
In such a case
we could just take the path of length $\pathnvert$,
blow up every vertex $v_{i}$ to $\pebsp$ vertices
$v_{i}^{1}, \ldots, v_{i}^{\pebsp}$,
and add edges
$\bigl( v_{i}^{j} , v_{i+1}^{j'}\bigr)$
for all $j, j' \in \intnfirst{\pebsp}$,
so that we get a sequence of
complete bipartite graphs $K_{\pebsp,\pebsp}$
glued together
as shown in fig:pike-unbounded-overview.
It is not hard to show that any reversible pebbling of this DAG would
have to do
$\pebsp$ parallel, synchronized pebblings of the paths
$\Set{ v_{1}^{j},  v_{2}^{j}, \ldots, v_{\pathnvert + 1}^{j}}$
for $j \in \intnfirst{\pebsp}$,
which would require space
$\bigomega{\pebsp \log \pathnvert}$,
whereas a pebbling would clearly only need space $\bigoh{\pebsp}$.

Path blown up to sequence of $K_{3,3}$-graphs.

graph of length $9$ and width $3$.

Modifications of path graphs to amplify difference between
reversible and pebbling price.

For bounded indegree it is not a priori clear what to do, however, or
indeed whether there should even be a multiplicative separation. But
it turns out that one can actually simulate a lower bound proof along
the same lines as above by considering a
graph as in fig:pike-overview,
with  $\pebsp$ parallel paths of length up to $\pathnvert$ and
with every path having an extra edge
fanning out to its “neighbour path” above (or at the bottom for the
top row) at each level. We will refer to this construction as a
of length $\pathnvert$ and width $\pebsp$
(where a path is a

maximally narrow
of width $1$).
It is easy to verify that the pebbling price of

a of width $\pebsp \geq 2$
is $\pebsp + 2$. We claim that the reversible pebbling price is
$\Bigomega{\pebsp \log ( \pathnvert / \pebsp)}$,

from which

To prove the reversible pebbling lower bound it is convenient to think
instead in terms of strategies in the . The
idea is that will stay put on the sink until has pebbled enough vertices so that there are no pebble-free paths
from any source vertex to the sink.
Intuitively,  the cheapest way for  to disconnect the
graph is with a straight cut over some layer.
When this happens, looks at the latest pebbled vertex
and compares the subgraph between the sources and the cut with the
subgraph between the cut and the sink. If more than half of the graph
is before the cut, jumps to the latest pebbled
vertex. If not, stays on the sink. This strategy is then
repeated on a graph of at least half the length. Since every cut by
requires $\pebsp$ pebbles, can survive for
$\pebsp \log \pathnvert$
rounds (except that the rigorous argument is not quite this simple,
and the slightly smaller factor
$\log ( \ell / \pebsp)$
in the formal statement of the theorem is in fact inherent).

§.§ PSPACE-Completeness of Reversible Pebbling

Moving on to technically more challenging material, let us next discuss
our -completeness result for reversible pebbling, which we
restate here more formally for the record.

Given a single-sink DAG $G$ of fan-in $2$ and a parameter $\pebsp$, it
is -complete to decide whether $G$ can be reversibly
pebbled in space $\pebsp$ or not.

In more detail,
given a QBF

$\QBF = Q_1 x_1 \, Q_2 x_2 \, \ldots \, Q_n x_n \, \, \fstd$,
where $\fstd$ is a 3
over variables $x_1, \ldots, x_n$,

there is a constructible
graph $\gadgetConst{\QBF}$
of fan-in $2$
and a computable number $\gamma(\QBF)$ such that
$\Persistentprice{\gadgetConst{\QBF}}=\gamma(\QBF)+\ib{\QBF \text{\
is \false}}$.

At a high level, our proof is similar to that
in [17]
for pebbling:
we build gadgets for

clauses, and universal and existential quantifiers, and then glue them
together in the right way so that pebbling through the gadgets
corresponds to verifying satisfying assignments for

universally and existentially quantified subformulas of

the QBF $\QBF$.
However, the execution of this simple idea
is highly nontrivial even in [17], and
we run into several additional technical difficulties when we want to
do an analogous reduction for reversible pebbling.

For starters, since the difference in pebbling price
for graphs $\gadgetConst{\QBF}$
obtained from true and false QBFs $\QBF$ is
just an additive $1$, we need
exact control over the pebbling price of all components used in the
reduction. For pebbling there is no  problem here—exact
bounds on pebbling price are known for quite a wide selection of
graphs—but in the
reversible setting this becomes an issue already for almost the simplest
possible graph: the complete binary tree of height $h$. An easy
inductive argument shows that the pebbling price of such a
tree is exactly $h+2$.
Since reversible pebblings find paths more challenging than do
pebblings, one could perhaps expect an extra additive
$\log h$ or so in the reversible pebbling bound. However, the
asymptotically correct bound turns out to be
$h + \bigtheta{\logstar h}$
as shown in [20],
and the upper and lower bounds on the multiplicative constant
obtained in that paper
are far from tight.

The story is even worse for the workhorse of the construction in
[17] (and many other pebbling results),
of height $h$,
which have $i$ vertices at level $i$ for $i=1, \ldots, h+1$,
and where
the $j$th vertex at level $i$ has incoming edges
from the $j$th and $(j+1)$st vertices at level $i+1$.
There is a very neat proof
in [9] that the pebbling price is again exactly $h+2$,
but for reversible pebbling price nothing has been known except that it
has to be somewhere between $h+2$ and
$h + \bigoh{\logstar h}$
(where the latter bound follows since any strategy for a complete
binary tree of height $h$ works for any DAG of height $h$).
As a crucial first step towards establishing
we exactly determine the reversible pebbling price of pyramids (and
also binary trees).

For $\Delta$ denoting a positive integer,
let $\pyrg$ be the function defined recursively as

\begin{equation*}
\pyrg(\pyrx) = \begin{cases}
& \text{if $\Delta=1$;}
\\
2^{\pyrg(\pyrx-1) + \pyrx - 2} + \pyrg(\pyrx-1)
& \text{otherwise;}
\end{cases}
\end{equation*}

and let the inverse $\pyrg^{-1}$ of this function be defined as

\begin{equation*}
\pyrg^{-1}(h)
= \minofset[\mid]{\pyrx}{\pyrg(\pyrx)\geq h}
\eqperiod
\end{equation*}

Then the  persistent pebbling price of a pyramid of height $h$, as
well as of a complete binary tree of height $h$,
is $h + \pyrg^{-1}(h)$,
$\pyrg^{-1}$ is efficiently computable.

Even though th:exact-trees-pyramids-overview is
an important step, we immediately run into new problems when trying to
use it as a building block in our reduction for reversible pebbling.
In the pebble
game a pebbling is any pebbling that reaches the
sink. For the reversible game there is a subtle distinction in
that we can ask whether it is sufficient to just reach the sink or
whether the rest of the graph must also be cleared of pebbles.
As discussed in sec:preliminaries, this leads to
two different flavours of reversible pebblings, namely
persistent pebblings,

which leave a pebble on the sink with the rest of the graph being empty,
and visiting pebblings, which just reach the sink (and
can then be thought to run in reverse after having visited the sink to
clear the whole graph including the sink from pebbles).  The pebblings
we actually care about are the persistent ones, but we cannot rule out
the possibility that subpebblings of gadgets are visiting
pebblings. Clearly, the difference in pebbling space is at most $1$,
but this is exactly the additive $1$

of which we cannot afford to lose control!
To make things worse, for pyramids it turns out that
persistent and visiting pebbling prices actually do differ except in
very rare cases.

Because of this, we have to build more involved graph gadgets for which we can
guarantee that visiting and persistent prices coincide.  These gadgets
are constructed in two steps.
First, we take a pyramid and append a path of suitable length,
depending on the height of the pyramid, to the pyramid sink, resulting
in a graph that we call a teabag. Second, we take such
teabags of smaller and smaller size and stack them on top of one
another, which yields a graph that looks a bit like a
Christmas tree. These Christmas tree graphs are
guaranteed to have the same pebbling price regardless of whether a
reversible pebbling is visiting or persistent.

With this in hand
we are almost ready to follow the approach

in the -completeness reduction for pebbling
in [17].
The idea is that we want to
build gadgets for the quantifiers in
a formula

of specified pebbling price

so that the only way to pebble the graph $\gadgetConst{\QBF}$ without
using too much space is to first pebble the gadget for
$\forall x$, then $\exists y$, et cetera, in the correct order until
all quantifier gadgets have been pebbled. Once we get to the clause
gadgets, we would like that the pebbles in the quantifier gadgets are
locked in place encoding a truth value assignment to the variables,
and that the only way to pebble through the clause gadgets without
exceeding the space budget is if every clause contains at least one
literal satisified by this truth value assignment.

In order to realize this plan,
there remains one more significant technical obstacle to overcome,
however. To try to explain what the issue is, we need to discuss the
-completeness reduction in [17]
in slightly more detail.

The way this reduction imposes an order in which the quantifier
gadgets have to be pebbled
is that pyramid graphs are included “at the bottom” of the

gadgets (topologically first
in order).  The source vertices of the quantifier gadgets

all appear in
such pyramids, and one has to pebble through these pyramids
to reach the rest of a gadget (where pebble placements encode variable
assignments as mentioned above).

In the first, outermost quantifier gadget the pyramids have large
height. In the second gadget the pyramid heights are slightly smaller, et
cetera, down to the last, innermost quantifier gadget where the
pyramids have smallest height. In this way, the pyramids are used to

“lock up” pebbles
and force a strict order of pebbling of the gadgets.
It can be shown that in order not to exceed the pebbling space budget,
any pebbling strategy has to start by pebbling the highest pyramids in
the first gadget. If the pebbling starts anywhere else in the graph,
this will mean that there are already pebbles elsewhere in the graph
when the pebbling strategy reaches the first, highest pyramids in the
outermost quantifier, but if so the overall
pebbling has to use up too much space to pebble through this pyramid.
One can also show that once the pyramids in the
outermost quantifier gadget have been pebbled, the pebbling cannot
proceed until the next quantifier gadget is pebbled. The pyramids in

this gadget
have smaller height, but there are also pebbles stuck in
place in the outermost gadget, meaning that pyramids must again be
pebbled in exactly the right order to stay within the space budget.

These properties can be used to normalize

pebbling strategies in the pebble game.
Without loss of generality, one can assume that any

strategy that starts pebbling a pyramid in a gadget will
complete this local pebbling in one go, leaving a pebble at the sink
of the pyramid, and will not place pebbles anywhere else until the
pebbling of the pyramid has been completed. Also, once a pyramid in a
quantifier gadget has been pebbled in this way, one can prove that it
will never be pebbled again since there is now at least one additional
pebble at some vertex later in the topological order in the graph, and
a repeated pebbling of the pyramid in question would therefore exceed
the space budget.  Thus, not only do the pyramids enforce that the
gadgets are pebbled in the right order—they also serve as
single-entry access points to the gadgets, making sure that each
gadget is pebbled exactly once.

There is no hope of building gadgets with such properties in a
reversible pebbling setting. It is

not true that a reversible pebbling
will pebble through a subgraph and then never return. Instead, as
already discussed

reversible pebblings will proceed in alternating
phases of interleaved “forward sweeps” and “reverse sweeps,” and
subgraphs will be entered also in reverse topological order.
Therefore, it is not sufficient to add “space-locking” subgraphs at
the source vertices of the gadgets.  Rather, we have to insert
“single-passage points” inside and in between the gadgets for
quantifiers and clauses.  We obtain such subgadgets by further
tweaking our Christmas tree construction so that it can also connect
two vertices in such a way that any pebbling has to “pay a
toll” to go through this subgraph.  We cannot describe these gadgets,
which we call s, in detail here, but mention
that the “space-locking” property that they have is that when the
entrance vertex is eliminated by having a pebble placed on that
vertex, then the cost of pebbling through the rest of the drops by $1$. This is critically used in the subgraph compositions
described next.

Assuming the existence of the necessary technical subgraph
constructions sketched above,

we can now describe the overall structure of our reduction from
quantified Boolean formulas to reversible pebbling
(where all parameters shown in the figures are fixed
appropriately in the formal proofs).
In the following

we denote a Christmas tree of (visiting and
persistent) pebbling price $r$ by the symbol in
fig:christmas-overview, where we only display the sink
vertex. We denote the gadget just discussed by the symbol in

We write $r$ to denote the toll parameter of the
, where a with toll $r$ has persistent price $r+2$,
but only $r+1$ if we do not count the source $a$ as part of the

Christmas tree.
-1.5cm 0cm -1.25cm 0cm

[Node] (s') at (0,0) ;
[Bank] (s) at (0,-) $r$;
(s.north west) to (s'.south west);
(s.north east) to (s'.south east);

-1cm 0cm -1cm 0cm

Legend for technical gadget building blocks.

For every variable $x_i$ we have a variable gadget as
shown in fig:variable-overview,
where we think of a
truth value
assignment $\partassign$
as represented by pebbles on
vertices $\{\bar\variable_{i},\variable'_{i}\}$ when
and on

$\{\variable_{i},\bar\variable'_{i}\}$ when
as shown in

Variable gadget.
-1cm 0cm -1cm 0cm

-1cm 0cm -1cm 0cm

-1cm 0cm -1cm 0cm

Gadget for variable $x_i$ and pebble positions
corresponding to truth value assignments.

For every clause $C_j$ we have a
clause gadget
as depicted in fig:clause-overview.

The vertices labelled $\ell'_{j,k}$ and $\ell_{j,k}$
in fig:clause-overview are identified with the corresponding
vertices for the positive or negative literal $\ell_{j,k}$
in the variable gadget
in fig:variable-overview.

If $\partassign$ satisfies a literal, then there is a pebble on the
entrance vertex of the corresponding , meaning that we can
pebble through the gadget for a clause containing that literal with
one less pebble than if $\partassign$ does not satisfy the clause.

Clause gadget.
-1cm 0cm -1cm 0cm

Conjunction gadget.
-1cm 0cm -1cm 0cm
centerminimum size=1.2cm

Gadgets for clauses and CNF formulas.

Existential quantifier gadget.
-1cm 0cm -1cm 0cm

γ_i - 5centerminimum size=1.4cm

Universal quantifier gadget.
-1cm 0cm -1cm 0cm

γ_i - 6
γ_i - 7centerminimum size=1.1cm

Quantifier gadgets for variable $x_i$.

To build the subgraph corresponding to a $3$ formula
$\fstd = \Land^{m}_{j=1} C_{j}$ we join
clause gadgets sequentially using the
conjunction gadget in fig:conjunction-overview.

For technical reasons we start by joining a dummy graph with the
first clause gadget, then we join the result to the second clause
gadget, and so on

up to the $m$th clause of $\fstd$.

The resulting graph has the property that if pebbles are placed on the
variable gadgets according to an assignment $\partassign$ that
satisfies $\fstd$, then the number of additional pebbles needed to
pebble the graph is one less than if the assignment is falsifying.

Finally we have one quantifier gadget for each
variable. To describe this part of the construction,

sort the variables indices
in reverse order
from the innermost to the outermost quantifier and
denote by $\QBF_{i}$ the

with just the $i$ innermost
so that

$\QBF_{0} =
\fstd =
\Land^{m}_{j=1} C_{j}$,

$\QBF_{i} = Q_i \variable_{i} \, \QBF_{i-1}$
for $Q_i \in \set{\forall, \exists}$,
and $\QBF=\QBF_{n}$.

We construct graphs $\gadget^{(i)}\defeq \gadgetConst{\QBF_{i}}$,
starting with $\gadget^{(0)}$ which is just the

subgraph corresponding to the CNF formula $\fstd$.

To construct $\gadget^{(i+1)}$ from $\gadget^{(i)}$ we
add an existential gadget as in
if $\variable_{i}$ is existentially quantified and a universal gadget as in
if $\variable_{i}$ is universally quantified.

An example of the full construction can be found in

Given this construction we argue along the same lines as in
in [17], although as mentioned above
there are numerous additional technical complications that we cannot
elaborate on in this brief overview of the proof.
We show that
given an assignment $\partassign_{i}$ to
$\set{\variable_{n},\ldots, \variable_{i+1}}$,
the number of additional pebbles needed to pebble $\gadget^{(i)}$
differs by $1$ depending on whether
$\QBF_{i}$ is true under the assignment $\partassign_i$ or not.

An existential gadget can be optimally pebbled by setting $x_i$ to any
value that satisfies $\QBF_{i-1}$. To pebble a universal gadget one
needs to assign $x_i$ to some value, pebble through the gadget, unset $x_i$ and
assign it to the opposite value, and finally pebble through the gadget
again, and both assignments to $x_i$ must yield satisfying assignments
to $\QBF_{i-1}$ in order for the pebbling not to go over budget.

Proceeding by induction,
we establish that the
complete graph
can be pebbled within the specified
space budget only if

is true, which yields

Example of
QBF-to-DAG reduction for

$\forall x_3 \exists x_2  \forall x_1
(x_1 \lor x_2 \lor x_3) \land
(\olnot{x_1} \lor x_2 \lor x_3) \land
(\olnot{x_1} \lor \olnot{x_2} \lor \olnot{x_3})

§.§ PSPACE-Inapproximability up to Additive Constants

Let us conclude the detailed overview of our contributions by
describing what is arguably the strongest result in this paper, namely
a strengthening of the
-completeness of pebbling
in [17] and of reversible pebbling in
th:pspace-construction to -hardness results for
approximating and reversible pebbling price to within any
additive constant $\pebsepconst$.

For any fixed positive integer $\pebsepconst$ it is -complete
to decide whether a  $G$ with fan-in $2$ has
(or reversible) pebbling price at most $\pebsp$ or at
least $\pebsp + \pebsepconst$.

We remark that it would of course have been even nicer to prove
multiplicative hardness results. We want to stress again, though, that to the
best of our knowledge these are the first results ever for hardness of
approximation of pebble games in a general setting. The fact that
these results hold even for could perhaps be taken both as an indication
that it should be possible to prove much stronger hardness results for
algorithms limited to polynomial time, and as a challenge to do so.

We obtain th:approx-both by defining and analyzing two graph
product constructions, one for and one for reversible
pebbling, which take two graphs and output product graphs with
pebbling price equal to the sum of the pebbling prices of the two
input graphs (except for an additive adjustment).

These graph products can then be applied
$\pebsepconst-1$ times to
the graphs obtained by the reductions from QBFs.

In the next theorem we state the formal properties of these graph

Given s
$\graphstd_i$ of fan-in 2 and size $n_i$ for $i=1,2$,
there are constructible s
of fan-in 2 and size $\Bigoh{(n_1 + n_2)^2}$ such that

* For pebbling price it holds that
$\blackprice{\blowupBlackConst{\graphstd_1}{\graphstd_2}} =
\blackprice{\graphstd_1} + \blackprice{\graphstd_2} - 1$.

* For reversible pebbling price it holds that
= \persistentprice{\graphstd_1} + \persistentprice{\graphstd_2} + 1$.

In the remainder of this section
we try to convey some of the flavour of
the arguments used to prove th:blowup-both and to give a sense
of some of  the technical obstacles that have to be overcome during
the analysis.

In what follows, we will mostly focus on the reversible pebble game,
since it is the technically more challenging and therefore also the
more interesting case. We will briefly discuss the product
construction for pebbling at the very end of the
We will refer to
as the outer graph
and $\graphstd_2$
as the inner graph
in the graph products

Intuitively, when taking the graph product of $\graphstd_1$
and $\graphstd_2$ the idea is to replace every vertex $v$ of the outer
graph $\graphstd_1$ with a (possibly slightly modified) copy of the inner
graph $\graphstd_{2}$. We will refer to this copy as the  in
the product graph.
The edges inside blocks are specified by the inner graph.
For edges
$(u,v)\in \edges{\graphstd_{1}}$
in the outer graph, we will need to connect the sink of the $u$-block
to vertices in the  in some way, and this is the crux of the

A first naive approach would be to add an edge from the sink of the
$u$-block to every source vertex of the  (as shown in the graph

product $\blowupNaiveConst{G_1}{G_2}$
in fig:overview-blowup).
Sadly, this simple idea fails for both and reversible
pebbling. It is not hard to find examples showing that the pebbling
price of
is not a function of the pebbling prices of
$G_1$ and $G_2$.

Examples of  graph products

as applied to a
pyramid of height $1$
(denoted $G_1$)
and a rhombus (denoted $G_2$).

A slightly more refined idea

is to add edges from the sink of the $u$-block to
all vertices
in the  (as in the

graph $\blowupExpensiveConst{G_1}{G_2}$
in fig:overview-blowup).

While we can observe right away that this idea is a non-starter, since
it will blow up the fan-in of the product DAG (and with no bounds on fan-in
the gap amplification would be trivial), it turns out that the
analysis yields interesting insights for the graph product that we
will actually use.  We will therefore employ this toy construction to
showcase some of the ideas and technical challenges that arise in the
actual proof of th:blowup-both.

Recall that we want to prove that
\Persistentprice{\blowupExpensiveConst{G_1}{G_2}} =
\pebsp_{1}+\pebsp_{2}-1$, where
$\pebsp_{i} =
\Persistentprice{\graphstd_{i}}$ for $i=1,2$.

To reversibly pebble
the product graph $\blowupExpensiveConst{G_1}{G_2}$

in at most this amount of space
we simulate a
minimal space pebbling of $\graphstd_1$,
where pebble placement or removal involving a vertex $v$
of $\graphstd_{1}$
invokes a complete pebbling
(or unpebbling)
of the copy of $\graphstd_2$ corresponding
to the .

This simulation uses at most $\pebsp_{2}$ pebbles

in the relevant
and at most  on sinks of other blocks, no more than $\pebsp_{1}+\pebsp_{2}-1$ pebbles in total.

Proving the lower bound
\Persistentprice{\blowupExpensiveConst{G_1}{G_2}} \geq
\pebsp_{1}+\pebsp_{2}-1$
is the difficult part.
Here the approach is to assume that we are given a complete
pebbling $\pebblingBlowUpExpensive$ of

and extract from it a  pebbling strategy $\pebbling$
for $\graphstd_{1}$ with the

that an expensive configuration in $\pebbling$ will also
help us to pinpoint an expensive configuration
in $\pebblingBlowUpExpensive$.

The most straightforward way to obtain a pebbling strategy $\pebbling$
for $\graphstd_{1}$ from $\pebblingBlowUpExpensive$ would be to make a
vertex $v$ in $\graphstd_{1}$ contain a pebble or not depending
only on the local pebble configuration of the
in $\blowupExpensiveConst{G_1}{G_2}$.
A natural idea is that $v$  should get a pebble if the
has a pebble on its sink and that this pebble should
be removed from $v$ when the corresponding block

has been emptied of pebbles.
If we apply this reduction to a pebbling $\pebblingBlowUpExpensive$
of $\blowupExpensiveConst{G_1}{G_2}$ we obtain a valid pebbling
of $\graphstd_{1}$.
The problem, however, is that $\pebblingBlowUpExpensive$ might locally
be doing a visiting pebbling (as defined in
of the copy of $\graphstd_{2}$  corresponding to the
as a way of moving pebbles on or off other blocks. The consequence of
this would be that a configuration of
maximal space $\pebsp_{1}$
in $\pebbling$ may result from  a configuration in
$\pebblingBlowUpExpensive$ that

space only
$\pebsp_{1}+\pebsp_{2} - 2$,
which is off by one compared to what we need and hence

the gap in pebbling price that we are trying to create.

If the visiting price of $G_2$ is the same as its persistent price,
then this problem does not arise, but since this does not hold for
graphs in general we need to

argue more carefully.
It is true that a visiting pebbling of a

copy of $G_2$
might save one pebble
as compared to a persistent pebbling, but whenever the sink contains a
pebble in a visiting but not persistent pebbling we know that there
must also be some other vertex

in $G_2$
that has a pebble (or else
the pebbling would be persistent by definition). We need to count such
pebbles also in our analysis.

To this end, we make a distinction between blocks that have paid the
persistent price

and the blocks that have paid the visiting price but not the
persistent price.

We say that

the copy of $G_2$ corresponding to some  is
, or just
for brevity,
at some point in time if the current pebble configuration
on its vertices requires reversible pebbling space $\pebsp_{2}-1$ to

be reached,
and that the  is

for short)
if the configuration

has reversible pebbling price $\pebsp_{2}$.

We can now define a more refined

way of projecting $\pebblingBlowUpExpensive$-configurations to
as follows.
If a  has paid the persistent
price, we put a pebble on the corresponding vertex $v$ in $G_1$. If a
block has paid just the visiting price but not the persistent price,

then we might still put a pebble on $v$ in $G_1$, but we only do so if
an additional (and slightly delicate) technical

condition[We do not want to get into too detailed a technical
argument here, but just for the record pebble configurations on

can be
projected to configurations on $G_1$ in two stages as follows:

Let $\pconf \subseteq \vertices{G_1}$
consist of all vertices $u$ such that the
configuration on the $u$-block in
is .

Let $\pconf' \subseteq \vertices{G_1} \setminus \pconf$ consist of
all vertices $v$ such that

(a) $v$ is not already surrounded by $\pconf$, and
(b) the configuration on the $v$-block in
is .

With this notation, the projected pebble configuration on $G_1$ is
defined to be
$\pconf \cup \pconf'$.]
holds for the pebbling configurations in the blocks corresponding to
predecessors of $v$. This technical condition is designed so that with

some additional work[One added technical complication that we
have to take care of here is that when we apply our
projection to a pebbling $\pebblingBlowUpExpensive$ of

to obtain a sequence of pebble configurations on $G_1$, this
sequence need not be a valid pebbling of $G_1$.
However, when the projected pebble configuration on $G_1$ changes
after a pebbling move we can insert a legal pebbling sequence
between the two projected configurations that passes through all
vertices of $G_1$ corresponding to blocks, where pebbles
are added in topological order and removed in inverse topological
order, and this local pebbling does not affect the overall

we are still able to extract a legal pebbling strategy for $G_1$ by
applying this  projection.

it will be the case
that every pebbling
move on a vertex in the outer graph $G_1$ is the result of the
copy of $G_2$ corresponding to some  paying the
persistent or visiting price.

The reversible pebbling $\pebbling$ thus extracted

will be  a persistent pebbling
of $G_1$ by construction, so it must contain a
configuration with $\pebsp_1$ pebbles. If this
configuration was reached because a block paid the persistent price,
then that block contains $\pebsp_2$ pebbles at a time when at least
$\pebsp_1-1$ other blocks have at least $1$ pebble each, which is the
lower bound that we are after. If the pebble configuration on $G_1$
in $\pebbling$ was reached because a block paid the visiting price,
however, then we are potentially still one pebble short. This is where
the additional technical condition mentioned above comes into play.
This condition on the predecessor blocks implies that we can find
at least one other block that also paid just the visiting price and
therefore must contain two pebbles. Summing up, we obtain one block
that  has at least $\pebsp_2-1$ pebbles, another block that has at
least $2$ pebbles, and at least $\pebsp_1-2$ additional blocks that
contain at least $1$ pebble each, and so the lower bound holds in this
case as well.
(Incidentally, this second case is the one where our first, naive,
graph product

We already observed, however, that the construction

does not get us very far
because it blows up the indegree of the resulting
product graph.

Therefore, in the actual proof of th:blowup-both
we have to consider a different construction.

Briefly, the idea is to start with the

graph $\blowupExpensiveConst{\graphstd_{1}}{\graphstd_{2}}$
but to bring the indegree down by splitting each vertex $w$
in every block into three vertices
All edges to $w$ from other blocks are routed to $w\extblowup$, all
edges from within the block are routed to $w\intblowup$,
and finally we add edges from $w\extblowup$ and $w\intblowup$
to $w\outblowup$.
This is the graph product
that we use to amplify differences in reversible pebbling price, and
that is also illustrated
in fig:overview-blowup.

Now we have to prove that the ideas just outlined work for this new
construction where each vertex has been replaced by a small “cloud” of
three vertices. The proof of this is much more technically challenging
than for the toy case discussed above, and there is no room to go
into details here.

At this point we want to switch gears a bit and briefly discuss an
application in proof complexity of the -hardness result for
reversible pebbling.

Perhaps the most well-studied proof system for proving the
unsatisfiability of, or refuting, CNF formulas is resolution
(we do not give any formal definition here, referring instead to, ,
[32] for the necessary details).
Every resolution proof can be represented as a DAG, and the
depth of this proof is the length of a longest path in
this DAG. The resolution depth of refuting an
unsatisfiable CNF formula
is the smallest depth of any resolution proof for the formula.
It was shown in [7] that computing the reversible
pebbling price of a graph of fan-in $\ell$
reduces to computing the resolution depth of a $(\ell+1)$-CNF
formula, and from this we can obtain the following corollary.

For any fixed positive integer $\pebsepconst$,
it is -complete to compute the resolution depth of refuting
$3$-CNF formulas up
to an additive error $\pebsepconst$.

Assuming that we can efficiently compute the resolution depth within
an additive error at most $\pebsepconst$, we show how to efficiently
compute the reversible pebbling price of any graph $\graphstd$
within an additive error  $\pebsepconst+1$, contradicting

Letting $\sink$ denote the unique sink of $\graphstd$, we consider a
new graph $\graphstd'$
which is $\graphstd$ augmented with a new successor $\sink'$
of $\sink$ ($\graphstd'=(V\cup\{\sink'\},E\cup\{(\sink,\sink')\})$
in formal notation).
The reversible
pebbling prices of $\graphstd$ and $\graphstd'$ differ by at most one.

For any graph $\graphstd$, [7] exhibits an
efficiently constructible unsatisfiable CNF
formula $\fstd_{\graphstd}$ that requires resolution depth equal to
the  reversible pebbling price of $\graphstd'$.  The width of the formula
is equal to the fan-in of $\graphstd$ plus one, so the result holds

Hence, if we could estimate the resolution depth of refuting
$\fstd_{\graphstd}$, the reversible pebbling price of
$\graphstd'$, within error $\pebsepconst$, this would yield an
estimate of the reversible pebbling price of $\graphstd$ to within error

We wrap up this section by switching back to pebbling and describing
the product construction
used to amplify pebbling price.
In this construction we also replace every vertex of $G_1$ with a copy
of $G_2$, but this time we append what we refer to as a
centipede graph to
the sink of every copy. A centipede is a path where each vertex but
the source has an extra, unique predecessor.
To connect the blocks, for every edge
$(u,v)\in E(G_1)$ we add edges from the sink of the $u$-centipede
to every source of the $v$-centipede. See
for an illustration.

Illustration of  pebbling graph product

$\pebsp_{i} = \Pebblingprice{\graphstd_{i}}$ for $i=1,2$,
we can pebble the graph product
in space $\pebsp_{1}+\pebsp_{2}-1$
by simulating an optimal pebbling of $G_1$: placing a pebble
on a vertex $v$ of $G_1$ is simulated by optimally pebbling the sink
of the corresponding , and removing a pebble is
simulated by removing the pebble on the sink.

This pebbling strategy is in fact optimal, and we can show this by
projecting any pebbling $\pebblingBlowUpBlack$ of

to a strategy $\pebbling$ for $\graphstd_1$. Each time any block
in $\blowupBlackConst{\graphstd_{1}}{\graphstd_{2}}$
contains $\pebsp_2$ pebbles, we pebble all vertices in $G_1$ whose
have pebbles and whose corresponding block in $\blowupBlack$ has a
pebble. When a block
in $\blowupBlackConst{\graphstd_{1}}{\graphstd_{2}}$
becomes empty, we remove the pebble from the
corresponding vertex in $G_1$. This projection has the property that when the
sink of a block is pebbled, the corresponding vertex in $\graphstd_1$
is also pebbled. Arguing similarly to in the reversible case, we show
that a strategy $\pebblingBlowUpBlack$ for $\blowupBlack$
using $\pebsp$ pebbles yields a strategy for $\graphstd_1$
using $\pebsp - \pebsp_2 +1$ pebbles. Therefore,
$\pebblingBlowUpBlack$ must use space at

hence the graph product
$\blowupBlackConst{\graphstd_{1}}{\graphstd_{2}}$ has the property
claimed in  th:blowup-both.

§ SEPARATION BETWEEN AND REVERSIBLE PEBBLING

In this section we discuss how the reversible pebbling price compares
with the one.

A reversible pebbling is also a legal pebbling, but the
opposite is not always true. However it is possible to construct a
reversible pebbling from a pebbling of time $\stoptime$ that
costs at most $ \log \stoptime $ times the price of the pebbling.

If graph $G$ has a pebbling of time $\stoptime$ and space
$p$, then $G$ has reversible pebbling price at most $p \ceiling{\log
\stoptime}$.

Let $\pebbling=(\pconf_{0},\ldots,\pconf_{\stoptime})$ be a pebbling of $G$ in space $p$. We show a strategy
for the Dymond–Tompa game on $G$ that allows to win in at
most $p\ceiling{\log \stoptime}$ rounds. Since
$\dtprice{G} = \persistentprice{G}$ this is sufficient.

keeps as an invariant an interval $[a,b]$ such that the
challenged pebble is in $\pconf_b$ and all vertices in $\pconf_a$
are pebbled but not challenged. Initially the interval is
$[0,\stoptime]$, and the strategy proceeds by bisection. At each
bisection step starts pebbling the vertices in the
configuration $\pconf_m$, with $m=(a+b)/2$, in any order. If
to a vertex $v$, then let $t$ be the smallest
number such that $a\leq t$ and $v\in \pconf_t$. now plays
in $[a,t]$. The interval halves because $t\leq m$. If in all moves, then plays in $[m,b]$ and the
interval also halves. When the interval becomes unit, the invariant implies that the move from $\pconf_a$ to $\pconf_b$ is
precisely a placement on the challenged vertex. Therefore, the
predecessors of the challenged vertex are pebbled and the game
ends. The game considers at most $\ceiling{\log \stoptime}$
configurations of $\pebbling$ and spends at most $p$ rounds on each.

We already know that the difference between the and
reversible pebbling price is unbounded. For example the pebbling price for a path of length $n$ is 2, while its reversible
pebbling price is $\bigtheta{\log n}$.

It follows that if a DAG $ G $ has depth $d$ and a pebbling
of time $ \stoptime $ and space $ p $, then

\begin{equation*}
\maxofexpr{p,\log d} \leq \persistentprice{G} \leq p\log \stoptime
\end{equation*}

We rule out the possibility of a simulation with only an additive
loss. Indeed we show a separation which is multiplicative in terms of
the logarithm of the size of the graph.

For any function $\pebsp(n) = \Bigoh{n^{1/2 - \epsilon}}$
where $\epsilon > 0$ is constant there are DAGs
$\set{G_n}_{n=1}^{\infty}$ of size $\bigtheta{n}$
with a single sink and fan-in $2$
such that
$\blackprice{G} = \bigoh{\pebsp(n)}$
$\persistentprice{G} = \bigomega{\pebsp(n) \log n}$
(where the hidden constant depends linearly on $\epsilon$).

The graphs that we use to witness the separation are the chains or
“wide paths”. A chain of width $w$ and length $\ell$
is a graph with $\ell+1$ layers, each having $ w $ vertices, where the
$i$-th vertex of a layer has two incoming edges from the $i$ and
$i+1$-th vertices of the previous layer (modulo $w$). The layers are
indexed from $0$ (the layer of the sources) to $\ell$ (the layer of
the sinks).

Since we want single sink graphs, we define a  of
width $w$ and length $\ell$ to be a chain of width $w$ and length
$\ell-w+1$ plus a pyramid of height $w-1$, where we identify the sinks of
the chain with the sources of the pyramid. The layers are indexed in
the same way as in the chain.
[Equivalently, a of length $ \ell $ and width $ w \leq
\ell$ is an induced subgraph of a chain of length $ \ell $ and width
$ w $. Fix one arbitrarily sink $ s $ in the chain: the subgraph
induced by vertices in $\ancnode{s}$ is indeed a of length $ \ell $ and width $ w $.]

graph of length 9 and width 3.

By pebbling each layer in order, we get a pebbling of a of width $w$ which uses $w+2$ pebbles.

The reversible pebbling of a depends on its length: a of
width $w$ and length $\ell$ has a reversible pebbling price
$\bigoh{w\log \ell}$. The idea is to simulate in parallel $ w $
copies of the reversible pebbling of the path of length $ \ell $,
which has price $ \bigoh{\log \ell} $.

We prove th:separation-standard-reversible by choosing for each $n$ a of width $w=s(n)$ and length $\ell=n/w$, and showing that this pebbling is essentially optimal.

A blocking set for a vertex set $ T \subseteq V(G)$ is
a subset of vertices $\stdbset\subseteq V(G)$ such that every path
from any source to any vertex in $T$ must contain a vertex in
$\stdbset$. We also say that $\stdbset$ blocks $T$.

A blocking set for all sinks of a directed acyclic graph $G$ is also
called a blocking set of $ G$.

We say that $\stdbset$ is a minimal blocking set if no subset of
$\stdbset$ is a blocking set.

A chain of width $ w $ has blocking sets with $ w $ vertices, all in
the same layer. It turns out that if a minimal blocking set has
vertices in multiple layers then it must be larger than that.

We say that a blocking set spreads over $d$ layers
when $a$ and $b$ are the lowest and the highest layers that the
blocking set intersects, respectively, and

A minimal blocking set of a chain that spreads over $d$ layers has
size at least $d+w-1$.

Consider such a minimal blocking set $\stdbset$.

Sort the layers of the chain from $ 0 $ (sources) to $ \ell $
(sinks) and

let $\firstlayernot$ and $\lastlayernot$ be the first and last layers with vertices
in $ \stdbset $, so that $ d=\lastlayernot -\firstlayernot +1$.

If $ \firstlayernot = \lastlayernot $ then $\stdbset$ must contain $ w $ vertices
and the Lemma holds. For the rest of the proof we assume $ \firstlayernot
< \lastlayernot$.

Define $f(i)$ to be the number of vertices at layer
$i$ that can reach a sink without passing through a vertex in $\stdbset$
(and are not in $\stdbset$ themselves).

By definition and minimality we get that $ f(i)=0 $ for all layers
$i\leq\firstlayernot$; $0 < f(i) < w$ for all layers $\firstlayernot < i \leq \lastlayernot$ and
$f(i)=w$ for $ i > \lastlayernot$.

Now we compute the intersection between $\stdbset$ and each

All vertices at layer $ \lastlayernot $ can reach the sink unless
they are in $ \stdbset$, therefore $ \stdbset$ must have $w-f(\lastlayernot)$
elements at the last layer. We claim that that $
\stdbset$ contains at least $f(i+1)-f(i)+1$ vertices from layer $i$,
for $\firstlayernot \leq i < \lastlayernot$.

Indeed, consider the set of the $f(i+1)$ vertices at layer $i+1$
that can reach a sink, and define $ N_{i} $ to be the set of their
predecessors in layer $ i $. Since $0<f(i+1)<w$, there are at least
$f(i+1)+1$ vertices in $N_{i}$.

A vertex in the $i$-th layer can reach a sink if and only if it is
in $N_i$ and not blocked by $B$.  Since we assumed that exactly $
f(i) $ of them can reach a sink, it must be that $ |N_{i}| - f(i)$
vertices are blocked by $ \stdbset $ right on layer $i$, i.e., they
are contained in $\stdbset$. Thus the intersection between $
\stdbset $ and layer $ i $ is $\setsize{B_i} \geq
\setsize{N_{i}}-f(i) = f(i+1)-f(i)+1$.

Using these facts we get that

\begin{equation*}
\setsize{\stdbset} =
\sum^{\lastlayernot}_{i=\firstlayernot} \setsize{B_i} \geq
w - f(\lastlayernot) +
\sum^{\lastlayernot-1}_{i=\firstlayernot} f(i+1)-f(i) + 1
=w +
f(\firstlayernot) + (d-1) = d+w-1 \eqperiod
\end{equation*}

We need to generalize lem:separator-is-large to a in
order to handle blocking sets within the pyramid part.

A minimal blocking set of a that spreads over $d$ layers has
size at least $d+q-1$, where $q$ is the width of the topmost layer.

If the blocking set is located on a single layer the lemma follows

Otherwise the proof is very similar to the one of
lem:separator-is-large, except that the intersection
between $\stdbset$ and its last layer $\lastlayernot$ has size at
least $q-f(\lastlayernot)$.

Now we prove the lower bound in th:separation-standard-reversible

The reversible pebbling price of a of width $w$ and length $\ell$ is at least $w\log (\ell/w)/2$.

We give a strategy by induction over $\ell$ that lasts
for $w\log (\ell/w)/2$ moves. Furthermore, the strategy as
long as the sink is connected to the sources. The base case is a
of length $\ell \leq w-1$, a pyramid of height $\ell$,
in which case the lemma holds vacuously.

We say that a directed path in the graph is  when
there are no pebbles on it except for its last vertex. A path from a
vertex to itself is a single vertex with a pebble on it.

During the game  focuses on a subgraph of
the , and keeps the following invariant at every round: there is a
path from the sink of this subgraph to the currently challenged

This concretely means that if places a pebble inside the
subgraph then plays according to its strategy for
that subgraph. Instead if the new pebble blocks the path
between the currently challenged pebble and the sink of the subgraph,
to the new pebble—essentially making the
path shorter.

If at some round focuses on a subgraph, in later rounds
will never challenge a vertex which is neither in the
subgraph nor in the path between its sink and the current

Let us now give the strategy for playing inside the subgraph.

As long as the sink of the subgraph is connected to the sources,

If the sink is disconnected from the sources by a blocking set,
decides to or to depending on the
position of the blocking set. Before describing how decides, we describe how the strategy continues in both cases.

We consider a minimal blocking set $\stdbset$ and note that the last pebbled vertex $u$ is in any blocking set. Indeed, there is a path from the sources to the sink that only has pebbles at $u$ and at the sink, otherwise the sink would have already been blocked.

We first consider the strategy after decides to .

Let $v$ be the vertex in the path from the sources to $u$ at
the layer immediately before all the vertices in $\stdbset$. From now on
focuses on the subgraph induced by the ancestors of $v$,
which is a .

This is not blocked, has no vertex in the blocking set
$\stdbset$, and there is a path from $v$ to the
challenged pebble $u$.

If decides to , it focuses on the with
sources at the layer immediately after all vertices in $ \stdbset $.
Again, this is not blocked, it is disjoint from the blocking set
$\stdbset$, and there is a path from its sink to the
currently challenged pebble.

It remains to describe how decides to or
to .

If the last layer of the blocking set has width $q < w$, then by lem:pike-separator-is-large it has size at least $q + d -1$.

In this case and focuses on a of length
$\ell-(q + d - 2)$.

Let $\dtprice{w,\ell}$ be the of a of width $w$ and length $\ell$.

Overall the strategy lasts for

\begin{equation}
\setsize{\stdbset} + \dtprice{w,\ell-(q+d-2)}
\geq q + d - 1 + w\log((\ell-(q+d-2))/w)/2 \geq w\log(\ell/w)/2
\end{equation}

Otherwise the blocking set $\stdbset$ has size at least $w+d-1 \geq w$
for some $ d\geq 1 $ and by lem:separator-is-large it spreads over at most $d$
layers, where $\firstlayernot$ is the lowest and $\lastlayernot$ is the highest, with $ d=\lastlayernot-\firstlayernot+1 $ and $m=(\firstlayernot+\lastlayernot)/2$.

If $m \leq \ell/2$, and focuses on the of
length $\ell - \lastlayernot - 1$ obtained considering only the vertices at
the layers from $ \lastlayernot + 1 $ to $ \ell $.

Overall the strategy lasts for

\begin{multline}
\setsize{\stdbset} + \dtprice{w,\lastlayernot-1}
\geq w + d-1 + w\log((\lastlayernot-1)/w)/2
\geq w + d-1 + w\log((\ell-d-1)/2w)/2 \\
= w/2\bigl(\log((\ell-d-1)/2w) + 2 + 2(d-1)/w\bigr)
\geq w/2\bigl(\log(\ell/2w)+1\bigr)
= w\log(\ell/w)/2
\end{multline}

If $m>\ell/2$, and focuses on a of length
$\firstlayernot-1$ obtained considering one vertex at layer $ \firstlayernot-1 $ which is
connected to the sources, and taking all vertices which have a path
toward such vertex.

Overall the strategy lasts for

\begin{multline}
\setsize{\stdbset} + \dtprice{w,\firstlayernot-1}
\geq w + d-1 + w\log((\firstlayernot-1)/w)/2 \\
\geq w + d-1 + w\log((\ell-d-1)/2w)/2
\geq w\log(\ell/w)/2
\end{multline}

Note that th:separation-standard-reversible follows if the width is $w=s(n)$ and the length is $\ell=n/w$ because $w\log(\ell/w)=w\log(n/w^2)=\bigtheta{w\log n}$ if $w=\Bigoh{n^{1/2-\epsilon}}$.

§ TIGHT BOUNDS FOR TREES AND PYRAMIDS

In this section we show matching upper and lower bounds for the
persistent pebbling price of complete binary trees and pyramids.
Asymptotically tight results for trees were given in

The pyramid graph of height $h$ has a vertex for every pair $(i,j)$
with $0 \leq i \leq j \leq h$. The sources are the vertices
$(0,j)$ for $j\geq 0$, the sink is the vertex $(h,h)$, and every
vertex $(i,j)$ for $i<h$ has one outgoing edge going left to vertex
$(i+1,j)$ if $j>i$ and one outgoing edge going right to vertex
$(i+1,j+1)$ if $j<h$.

A pyramid can be obtained from a complete binary tree of height $h$ by
identifying together some of its vertices, in such a way that the left
and right predecessors of two vertices that get identified, get
pairwise identified as well.

For this reason an upper bound for binary trees also holds for the
pyramids, and a lower bound for pyramids also holds for binary trees.

In the following, let $p = h+\pyrx$ be the persistent price of a
pyramid. A pyramid of height $h$ has pebbling price $h+2$
[9], which means that in the
pebbling only two extra pebbles are needed compared to the
height of the pyramid. In a similar fashion $\pyrx$ can be interpreted
as the extra space needed by persistent pebbling, with respect to
pyramind height.

We want to estimate the height of the pyramid that has persistent
pebbling with at most $\pyrx$ extra pebbles.

Consider $\Delta \in \Nplus$ and let $\pyrg(\pyrx)$ be the function
defined by the following recursion,

\begin{equation*}
\pyrg(\pyrx) = \begin{cases}
0 & \text{if $\Delta=1$}\\
2^{\pyrg(\pyrx-1) + \pyrx - 2} + \pyrg(\pyrx-1) & \text{otherwise.}
\end{cases}
\end{equation*}

We define its inverse as

\begin{equation*}
\pyrg^{-1}(h) = \min\{\pyrx \mid \pyrg(\pyrx)\geq h\}.
\end{equation*}

We show that $\pyrg(\pyrx)$ is the maximum height of a pyramid that can be persistently pebbled using $\pyrx$ pebbles on top of $h$. Observe that $\pyrg(\pyrx)=\bigomega{\underbrace{2^{2^{\cdots^2}}}_\pyrx}$, therefore $\pyrg^{-1}(h) = \bigoh{\log^* h}$.

We can compute $\pyrg^{-1}(h)$ in time ${(\log h)}^{\bigoh{1}}$ and
space $\bigoh{\log h}$.

If $h=0$ then $\pyrg^{-1}(0)$ is $1$ by definition.

If $h>0$ then
we need to find the smallest $\pyrx>1$ such that
$h \ge \pyrg(\pyrx)$.

We start from $\pyrx\defeq{2}$ and go upward. At each step we keep in
memory the value $\pyrg(\pyrx-1)$, which is smaller than $h$,

and we test the condition

\begin{equation*}
h < \pyrg(\pyrx)
\quad
\text{equivalent to}
\quad
\lfloor\log(h - \pyrg(\pyrx-1))\rfloor
\pyrg(\pyrx-1) + \pyrx - 2 \eqperiod
\end{equation*}

The latter test can be achieved in time in $\log h$ by checking the
length of the bit representation of $h - \pyrg(\pyrx-1)$.

If the test fails we output $\pyrx$ otherwise we store the value
$\pyrg(\pyrx)$, we fix $\pyrx\defeq \pyrx+1$ and we continue.

We can do the whole computation by storing at most $4$ numbers less
than $h$, each step is polynomial in the length of the binary
representation of the numbers involved, and we need to do at most
$\bigoh{\log^* h}$ steps.

The persistent pebbling price of a binary tree of height $h$ and a
pyramid of height $h$ is $h + \pyrg^{-1}(h)$.

To prove the theorem we need the exact value of the persistent
pebbling price of paths.

The persistent pebbling price of a path of length $h$ (with
$h+1$ vertices) is $\floor{\log(h)} + 2$.

The persistent pebbling price of a complete binary tree of height
$h \le \pyrg(\pyrx)$ is at most $h+\pyrx$.

We are going to prove the lemma by induction over $ h $.

For the base case we observe that a binary tree of height $0$ can be
pebbled with $1$ pebbles.

For the general case we assume the statement of the lemma for height
$i<h$, and we show that the surrounding pebbling price of the
complete binary tree of height $h$ is at most $ h+ \pyrx -1$.

Proposition <ref> immediately implies
the lemma for height $h$.

Let us denote the root by $v_h$ and the right child of $v_i$ by
$v_{i-1}$. The strategy is as follows. First we persistently pebble
the left child of $v_i$ for $i$ from $h$ down to $k \defeq \pyrg(\pyrx -1) +
1$, in this order. By the induction hypothesis $(i-1) + \pyrx$ pebbles
are enough to persistently pebble the left child of $v_i$, and there
are $h - i$ pebbles left on the rest of the graph from previous steps. So we are
within the bound $h-1+\pyrx$, and after the last step we have $h -
(k-1)$ pebbles on the tree.

Then we persistently pebble $v_{k-1}$, the right child of
$v_k$. Since $k-1 = \pyrg(\pyrx-1)$, by induction hypothesis $(k-1)+(\pyrx-1)$
pebbles are enough and we are within the bound.

Let $j \defeq h-k+1$. So far we used $j+1 = h - k + 2$ pebbles.

Finally we surround the sink of path $(v_k, v_{k+1}, \ldots,
v_h)$, which has $j$ vertices, using $\floor{\log(j-1)} + 1$

Observe that by
construction $j - 1 = h - k \le \pyrg(\pyrx) - \pyrg(\pyrx-1) - 1 <
2^{\pyrg(\pyrx-1) + \pyrx - 2}$, hence we have the bound
$\floor{\log(j-1)} < \pyrg(\pyrx-1) + \pyrx - 2$. Counting the total
number of pebbles in the graph gives $\bigl( h - k + 2 \bigr) +
\floor{\log(j-1)} + 1 \le \bigl( h - \pyrg(\pyrx-1) + 1 \bigr) +
\bigl( \pyrg(\pyrx-1)+ \pyrx - 3 \bigr) + 1 = h + \pyrx - 1$

We prove the lower bound for a slight generalization of pyramids in order to
obtain a lower bound on the visiting price in addition to the persistent price.

An $(h,\ell)$-teabag is the union of a pyramid of height $h$ and a path of length $\ell$, where we identify the sink of the pyramid and the source of the path.

Observe that an $(h,0)$-teabag is a pyramid.

For the lower bound we will also need the following basic fact about
pyramids. Recall that a blocking set is a subset of vertices
$\stdbset\subseteq V(G)$ such that every path from any source to the
sink must contain a vertex in $\stdbset$. Also recall that a directed
path in the graph is when there are no
pebbles on it except for its last vertex.

Consider a blocking set $\stdbset$ on a pyramid of height $ h$;
consider a vertex $ v $ at level $ k $ such that there is a path
between $v$ and the sink whose intersection with $\stdbset$ is at most
$\{v\}$. Let $ U $ be the set of vertices in the sub-pyramid rooted at
$ v $. Then $\setsize{\stdbset\setminus{U}} \geq h-k$.

Pick an arbitrary path which starts at vertex $v$, reaches the
pyramid sink and does not intersect $\stdbset$ anywhere other than in

Denote such path as $(v_{k}, v_{k+1}, \ldots, v_{h})$ where $v_{k}$
is another name for $v$ and $v_{h}$ is the sink. Each $v_{i}$ is at
height $i$ in the pyramid.

On pyramids there is a natural notion for edges to go either left or

For each $i>k$ we define the path $\DAGNamePath_{i}$ as follows: if
edge $(v_{i-1},v_{i})$ goes right then $\DAGNamePath_{i}$ is the
unique path that starts at a source vertex, always goes left, and  ends at

if edge $(v_{i},v_{i-1})$ goes left then $\DAGNamePath_{i}$ is the unique path
that starts at a source vertex, always goes right, and ends at $v_{i}$.

It is easy to verify that none of $\DAGNamePath_{h}, \ldots, \DAGNamePath_{k+1} $
intersects any of the vertices in $U$, and that these paths are all
pairwise vertex disjoint.

Since $\stdbset$ is a blocking set it must contain one vertex for
each $\DAGNamePath_{i}$ and the proposition follows.

The persistent pebbling price of the $(h,\ell)$-teabag is at least $h+\pyrx+1$ if either of the following holds:

* $h>\pyrg(\pyrx)$,

* $h > \pyrg(\pyrx-1)$ and $\ell>\pyrg(\pyrx)-h$.

We define a strategy for the Dymond–Tompa game by
induction over $h$ and $\ell$ in this order. Furthermore this
strategy on the sink until blocks the graph. For
the base case $h=0$, the statement is trivial.

Assume that the last move blocks the graph, meaning that
the currently pebbled vertices form a blocking set, and fix
$\stdbset$ to be a minimal one. The vertex $v$ pebbled at that round
must be in $\stdbset$. We have two cases depending on $k$ the layer
of vertex $v$.

* Case $ k > \pyrg(\pyrx-1) $: to $v$. The pebble
on $ v $ blocks the sources from the sink, so there must be a path between $ v $ and a source.

Let $ U $ be the set of pebbles contained in the vertices of $P_v$,
the subgraph of predecessors of $ v $ (notice that $ v \in U$).

Consider a new game on $P_{v}$, in which the first actions of
are to pebble $ U\setminus\{v\}$ in any order, while
on $ v $. The set $ U\setminus\{v\} $ does
not block the subgraph.

If $k\geq h$ then the new sub-game ends in at least $h + \pyrx$ steps, and
the total number of rounds is at least $1+ h + \pyrx$.

Otherwise $v$ is inside the pyramid, and the new sub-game ends in $k
+ \pyrx$ steps. We use Proposition <ref> to claim
that $\setsize{\stdbset\setminus{U}} \geq h-k$. So in
total the rounds in the game are at least

\begin{equation*}
\underbrace{1}_{\text{challenge to sink}} +
\underbrace{\setsize{\stdbset\setminus{U}}}_{\text{outside
$P_{v}$}} +
\underbrace{k+ \pyrx}_{\text{subgame on $P_{v}$}} \geq h+\pyrx+1 \eqperiod
\end{equation*}

I really don't like underbraces. Can't we just remove them
and explain equations properly in running text?

* Case $ k \leq \pyrg(\pyrx-1) $: there is a path of length $h-k+\ell$
from $v$ to the sink having only a pebble on each end. So any optimal
strategy must contain a strategy for playing on the
semiopen path of length $ h-k+\ell-1 $ from one unpebbled successor
of $v$ to the sink.

Fix $q=\floor{\log(h-k+\ell-1)}$, the sub-game on the path of length
$ h-k+\ell-1 $ lasts at least $q+2$ rounds (see
lem:PathGraphs). The initial challenge on the sink of the
graph is part of this sub-game, but all moves on $\stdbset$ are not,
so the total number of rounds is

\begin{equation*}
\underbrace{\setsize{\stdbset}}_{\text{blocking set}} +
\underbrace{q+2}_{\text{subgame on path}} \geq
\underbrace{h - k + 1}_{\text{blocking set}} +
\underbrace{\pyrg(\pyrx-1)+\pyrx}_{\text{subgame on path}} \geq
h +\pyrx+1 \eqperiod
\end{equation*}

The bound on $\setsize{\stdbset}$ holds because
Proposition <ref> on vertex $ v $ implies
$\setsize{\stdbset\setminus\set{v}} \geq h-k$. The bound on $q+2$
holds because by hypothesis

$ h-k+\ell -1 \geq \pyrg(\pyrx) - \pyrg(\pyrx-1)$,

which implies that

$q \geq \floor{\log(\pyrg(\pyrx)-\pyrg(\pyrx-1))} \geq
\pyrg(\pyrx-1)+\pyrx-2$.

The persistent pebbling price of a pyramid of height $h>\pyrg(\pyrx-1)$ is
at least $h+\pyrx$.
The visiting price of a pyramid of height $h=\pyrg(\pyrx)$ is at least

Lemma <ref> claims the first statement.  The
second one holds because if the pyramid of height $\pyrg(\pyrx)$ had
visiting price $h+\pyrx-1$, then the $(\pyrg(\pyrx),1)$-teabag would
have persistent pebbling price $h+\pyrx$, which contradicts
Lemma <ref>.

§ TECHNICAL CONSTRUCTIONS

In order to discuss lower bounds on pebbling price we need to identify
expensive pebbling configurations, namely the configurations that are
expensive to reach from the empty configuration.

We will often use the reverse direction, that the empty
configuration cannot be reached without passing through an expensive

A configuration $\pconf$ is  if

A configuration $\pconf$ is  if

§.§ Christmas Tree Construction

This section builds on the pyramid graphs to provide a graph $T_{r}$
with equal visiting and persistent prices $r$ for every
$r\in \N^{+}$. As a preliminary step we show a graph $G_{p}$ with
persistent price $p$ for every $p\in \N^{+}$.

There is a family of graphs $\{ G_p \}_{p \in \N^+}$ such that

* $\persistentprice{G_p} = p$;

* $G_p$ has in-degree at most two and a unique sink; and

* $G_p$ is computable given $p$, and $G_p$ has at most
$p^2$ nodes.

The value of $\pyrg^{-1}(h)$, which is the extra pebbling price of pyramids with respect to the
height, increases only when $h=\pyrg(\pyrx)+1$.

Therefore the persistent pebbling price of a pyramid increases by 1 unless
$h=\pyrg(\pyrx)+1$, in which case it increases by 2.

If $p = h + \pyrg^{-1}(h)$ for some $h \in \N$ we let $G_p$
be the pyramid graph of height $h$.

In this way $G_{p}$ is defined for every $p>0$, unless
$p = h + \pyrg^{-1}(h) + 1$ for some $h =\pyrg(\pyrx)$.

In this case we let $G_p$ be the $(h,1)$-teabag which, by
Lemmas <ref> and <ref>, has
persistent pebbling price $p = h + \pyrg^{-1}(h) + 1$.

We want a computable family of graphs $\{ T_\bank \}_{\bank \in
\N^+}$ with matching visiting price and persistent price, $\visitprice{T_\bank} = \persistentprice{T_\bank} = \bank$.
The idea is to stack up $\bank$ appropriately chosen graphs, so that any
visiting or persistent pebbling strategy has to spend one pebble per graph.

We will use $r$ graphs from the family $\{ G_p \}_{p \in \N^+}$
where each $G_p$ has persistent pebbling price $p$, as constructed
in lem:ModifiedPyramids.

The resulting graph is a stack of modified pyramids of increasing
sizes. If there is justice in this world, the resulting graph should
be called a Christmas Tree;

though a graph theorist may have a hard time calling
this a “tree”.

Illustration of a Christmas Tree in Construction <ref>.

[Christmas Tree]

Let $\{ G_p \}_{p \in \N^+}$ be given as in lem:ModifiedPyramids.
Given $\bank \in \N^+$, construct a graph $T_\bank \defeq (V, E)$ as follows.
Its vertex set $V \defeq V^1 \disjunion V^2 \disjunion
\dotsb \disjunion V^\bank$ is a disjoint union of $\bank$ layers, where
for $1 \le \timet < \bank$ the $\timet\th$ layer is a copy of
$G_{\bank - \timet}$ with vertices $V^\timet \defeq V(G_{\bank - \timet})$,
and the top-most layer is another copy of
$G_1$ with vertices $V^\bank \defeq V(G_1)$.

Its edge set $E \defeq \intraedges \disjunion
\interedges$ consists of intra- and inter-layer edges.

The intra-layer edges $\intraedges \defeq E^1 \disjunion
E^2 \disjunion \dotsb \disjunion E^\bank$ come from the
corresponding copies of $G_p$, for $1 \le \timet < \bank$ the edges on the $\timet\th$ layer
$E^\timet$ are copies of $ E(G_{\bank - \timet})$ and
and the edges on the top-most layer $E^\bank$ are copies of $

The inter-layer edges

$\interedges$ connect, for each
$1 \leq \timet \leq \bank -2 $, the sink of the subgraph at
layer $\timet$ with all sources of the subgraphs at layer
$\timet+1$ and $\timet+2$, and also connect the sink of the copy
of $G_{1}$ at layer $\bank-1$ with the sources of the copy of
$G_{1}$ at layer $\bank$.

The family of graphs $\{ T_\bank \}_{\bank \in \N^+}$ satisfies

* $\visitprice{T_\bank} = \persistentprice{T_\bank} = \bank$;

* $T_\bank$ has in-degree at most two and a unique sink; and

* $T_\bank$ is computable given $\bank$, and $T_\bank$
has at most $\bank^3$.

For Item 3, note that each of the $\bank$ layers has at most $\bank^2$

For Item 2, if $v$ is a node in $T_\bank$ we have two cases
depending on whether $v$ is some layer's source node or not.

If it is, then at most two inter-layer edges from lower layers
point to $v$, and no intra-layer edge does.

If $v$ is not a source on any layer then only two intra-layer
edges point to it, since all $G_{p}$ have fan-in at most 2.

The only sink of $T_\bank$ is the sink of layer $\bank$.

To see that $\surroundprice{T_\bank} \le \bank - 1$, and thus that
$\persistentprice{T_{\bank}} \leq \bank$, persistently pebble the
sink node of $G_{\bank-\timet}$ on layer $\timet$, for $\timet$
from 1 to $\bank - 1$, keeping only the pebbles on the sinks of
the previous layers.

To persistently pebble layer $\timet$ takes $\bank - \timet$
pebbles, assuming there is a pebble on each of the sinks of the
$\timet-1$ lower layers, so in total $\bank - 1$ pebbles suffice.

Note that
$G_1$ is a single node, hence when the sinks of the lower layers
are all pebbled the sink of $T_\bank$ is surrounded.

The bound $\persistentprice{T_\bank} \le \bank$ follows by
Proposition <ref>.

To see that $\visitprice{T_\bank} \ge \bank$, we argue that when
visiting layer $\bank$ there is a pebble configuration
on each of the previous layers (see
Definition <ref>).

In particular, any layer with a pebble on the sink has
a configuration and if a configuration is ,
then it contains a pebble.

Given a pebbling configuration on $T_\bank$, for the rest of this
proof we say that layer $\timet$ is  if
the configuration, restricted to the corresponding subgraph, is
for the subgraph.

[Christmas Tree Locker]

Consider any pebbling that uses less than $\bank$ pebbles.

In such a pebbling, whenever some layer $(\timet-1)$ and layer
$\timet$ contain some pebbles, for $2 \le \timet\le \bank$, then
layers $1, \ldots, \timet - 2$ are all .

The claim is true for $\timet = 2$ vacuously, establishing the base case.
When $\timet > 2$, consider a time that layer $\timet$ starts to have a
a source node on layer $\timet$ is pebbled, hence there are pebbles on
the sink nodes of layers $\timet-1$ and $\timet-2$.
Thus layers $\timet-1$ and $\timet-2$ are and each has a pebble.
Induction hypothesis (on $\timet-1$) further says that layer $\eta$ is
for any $1 \le \eta < \timet - 2$.
As long as there are pebbles on layers $\timet$ and $\timet-1$, all lower
layers remain :
for $1 \le \eta \le \timet - 2$, to unlock layer $\eta$ takes
$\visitprice{G_{\bank-\eta}} \ge \surroundprice{G_{\bank-\eta}} = \bank - \eta - 1
\ge \bank - \timet + 1$ pebbles (recall Eq. (<ref>)), but
there are $\timet-1$ pebbles on layers other than $\eta$, which cannot be
done with less than $\bank$ pebbles.

Assume for some $\bank \ge 2$, the sink node of layer $\bank$ is pebbled
using less than $\bank$ pebbles.
When a source node of layer $\bank$ is pebbled, there is a pebble on the
sink node of layer $\bank - 1$.
Claim <ref> shows that there is a pebble on layer $\eta$ for $1
\le \eta \le \bank - 2$, for a total of $\bank$ pebbles, contradicting
that less than $\bank$ pebbles are used.
This shows $\visitprice{T_\bank} \ge \bank$ for $\bank \ge 2$, and the case for
$\bank = 1$ is obvious.

In the end we get that

\begin{equation}
\bank \le \visitprice{T_\bank} \le \persistentprice{T_\bank} = \surroundprice{T_\bank} + 1 \le \bank
\end{equation}

by equation <ref> and
Proposition <ref>, which gives Item 1.

§.§ Molding

Given a graph $G$ we want to construct a graph $\mold(G)$ with
a special source $s$ and a single sink, such that any pebbling that
visits the sink must go through a configuration with at least
$\visitprice{\mold(G)}$ pebbles, one of which is on vertex $s$.

Example of con:Molding: molding of a pyramid of height 1.

Given a graph $G$, we construct a graph $\mold(G)$ as follows.
For every vertex $v \in V(G)$, we add to $\mold(G)$ two vertices
$v\inmold$ and $v\outmold$, and a directed edge
$(v\inmold, v\outmold)$.

Also, for every edge $(u,v) \in E(G)$, we add to $\mold(G)$
a corresponding edge $(u\outmold,v\inmold)$.

Finally we add to $\mold(G)$ a special new vertex $s$ that we
connect to all vertices $v\outmold$, for every
$v \in V(G)$ we add edge $(s, v\outmold)$ to $\mold(G)$.

\defeq
\{ s \} \disjunion
\bigl\{ v\inmold, v\outmold \where v \in V(G) \bigr\}$
$E(\mold(G)) \defeq E_1 \disjunion E_2 \disjunion E_3$,
$E_1 \defeq \bigl\{ (v\inmold, v\outmold) \where v \in V(G)
\bigr\}$,
$E_2 \defeq \bigl\{ (u\outmold, v\inmold) \where (u,v) \in E(G)
\bigr\}$
$E_3 \defeq \bigl\{ (s, v\outmold) \where v \in V(G) \bigr\}$.

By construction, if $G$ has in-degree at most two and a unique sink then so does

Given a graph $G$, the graph $\mold(G)$ has the following properties.

* $\Persistentprice{ \mold(G) } \le \persistentprice{G} + 2$; and

* For any visiting pebbling $\pebbling' = \langle \pconf'_0,
\pconf'_1, \dotsc, \pconf'_{\stoptime} \rangle$ of $\mold(G)$, there
is a configuration $P'_b$ (for some $0 \le b \le \stoptime$) using at
least $\visitprice{G} + 2$ pebbles and containing $s$.

For Item (1), fix any persistent pebbling $\pebbling$ of $G$.
Simulate the pebbling $\pebbling$ as a persistent pebbling $\pebbling'$ of
$\mold(G)$ as follows.
First, pebble the special source $s$ of $\mold(G)$ in $\pebbling'$.
Afterwards, whenever there is a move in $\pebbling$ to pebble a node $v
\in V(G)$, make a phase of three moves in $\pebbling'$:
pebble $v\inmold$, pebble $v\outmold$, unpebble $v\inmold$.
Similarly, whenever there is a move in $\pebbling$ to unpebble a node $v
\in V(G)$, make a phase of three moves in $\pebbling'$:
pebble $v\inmold$, unpebble $v\outmold$, unpebble $v\inmold$.
If the current configuration in $\pebbling$ is $\pconf$, and
the configuration in $\pebbling'$ at the end of a phase is $\pconf'$, then
$\pebbling'$ maintains
the invariant that $\pconf' = \{ s \} \union \bigl\{ v\outmold
\where v \in \pconf \bigr\}$.
As a result, $\pebbling'$ is a legal pebbling on $\mold(G)$:
whenever $v\inmold$ is pebbled or unpebbled, all its predecessors
$\prednode{v\inmold} = \bigl\{ u\outmold \where u \in \prednode{v}
\bigr\}$ have pebbles in $\pconf'$,
since $\prednode{v}$ have pebbles in $\pconf$;
whenever $v\outmold$ is pebbled or unpebbled, its predecessors $s$ and
$v\inmold$ have pebbles.
If we add a final move in $\pebbling'$ to unpebble $s$, then $\pebbling'$
persistently pebbles $\mold(G)$.
Note that whenever $\pebbling$ pebbles or unpebbles $v \in V(G)$ to get to
configuration $\pconf$, the simulating pebbling $\pebbling'$ uses at most
two more pebbles to get to $\pconf'$, namely $s$ and $v\inmold$.
Hence $\Persistentprice{ \mold(G) } \le \persistentprice{G} + 2$.

For Item (2), we start with a visiting pebbling $\pebbling' = \langle \pconf_0',
\pconf_1', \dotsc, \pconf_{\stoptime}'\rangle$ of $\mold(G)$ and
we construct a visiting pebbling $\pebbling$ of $G$.

We now define two projection operators that turn pebble
configurations for $\mold(G)$ into configurations for $G$.
Let $\outmoldprojTime{\timet} \defeq
\bigl\{ v \in V(G) \where v\outmold \in \pconf_\timet' \bigr\}$
be the projection of $\pconf_\timet'$ to $V(G)$ via $v\outmold$, and
$\anymoldprojTime{\timet} \defeq
\bigl\{ v \in V(G) \where v\inmold \in \pconf_\timet' \text{ or
} v\outmold \in \pconf_\timet' \}$ be the projection of $\pconf_\timet'$
to $V(G)$ via $v\inmold$ or $v\outmold$.

By definition $\outmoldprojTime{\timet} \subseteq
\anymoldprojTime{\timet}$.

Whenever a vertex of $\mold(G)$ is pebbled or unpebbled during
a pebbling step from  $\pconf_\timet'$ to $\pconf_{\timet+1}'$,

* if the vertex is $s$, then both
$\outmoldprojTime{\timet}=\outmoldprojTime{\timet+1}$ and

* if the vertex is $v\inmold$ for some $v \in V(G)$, then
$\outmoldprojTime{\timet} = \outmoldprojTime{\timet+1}$
but $\anymoldprojTime{\timet}$ may differ from

* if the vertex is $v\outmold$ for some $v \in V(G)$, then
$\anymoldprojTime{\timet} = \anymoldprojTime{\timet+1}$
but $\outmoldprojTime{\timet} \not=
\outmoldprojTime{\timet+1}$.

To construct $\pebbling$, we analyze in order each configuration
$\pconf'_{t}$ in $\pebbling'$. Depending on how the sequences of
$\outmoldprojTime{\timet}$ and $\anymoldprojTime{\timet}$ evolve,
we may append new configurations to $\pebbling$.

In the following $\eta$ is the index of the last configuration
added to $\pebbling$ and $\timet$ is the configuration of
$\pebbling'$ under analysis. We maintain the
following invariants:

* $\outmoldprojTime{\timet} \subseteq \pconf_\eta$; and

* for any $v$ in $\anymoldprojTime{\timet} \symmdiff \pconf_\eta$

it holds that $\prednode{v} \subseteq \outmoldprojTime{\timet}$.

Initially at $\timet=0$ and $\eta=0$,
$\pconf_\timet' = \outmoldprojTime{\timet} =
\anymoldprojTime{\timet} = \pconf_\eta = \emptyset$,
so the invariant holds for $\timet=0$.

Consider a pebbling move in $\pebbling'$ from $\pconf_\timet'$ to

* If $\anymoldprojTime{\timet} = \anymoldprojTime{\timet+1}$
and $\outmoldprojTime{\timet} = \outmoldprojTime{\timet+1}$ the
construction does not append any new $\pconf_\eta$ and the
invariant is preserved.

* If $\anymoldprojTime{\timet} \not=
\anymoldprojTime{\timet+1}$ then we are in case (ii) above, so
$\outmoldprojTime{\timet}$ does not
change and some node $v\inmold$ is pebbled or unpebbled. Hence the
current configuration $\pconf_\timet' \supseteq \prednode{v\inmold} =
\bigl\{ u\outmold \where u \in \prednode{v} \bigr\}$, thus
$\outmoldprojTime{\timet} \supseteq \prednode{v}$.
The construction does not append a new $\pconf_{\eta}$ and
the invariant is preserved.

* If $\outmoldprojTime{\timet} \not=
\outmoldprojTime{\timet+1}$
then we are in case (iii) above, so
$\anymoldprojTime{\timet}$ does not change and some node $v\outmold$
is pebbled or unpebbled.

The construction appends to $\pebbling$ the two sequences of
moves (“Eras”) described below. After each move
$\anymoldprojTime{\timet} \symmdiff \pconf_\eta$ gets smaller.

Note that for any $u \in \anymoldprojTime{\timet} \symmdiff
\pconf_\eta$, the invariant gives $\prednode{u} \subseteq
\outmoldprojTime{\timet} \subseteq \pconf_\eta$, so
they can be pebbled or unpebbled in $\pconf_\eta$.

Unpebble Era while $\pconf_\eta \setminus
\anymoldprojTime{\timet} \ne \emptyset$,
pick any $u \in \pconf_\eta \setminus \anymoldprojTime{\timet}$, and
unpebble $u$ in $\pebbling$ (increment $\eta \defeq \eta + 1$ and
then set $\pconf_\eta \defeq \pconf_{\eta - 1} \setminus \{ u \}$).
Since $\outmoldprojTime{\timet} \subseteq \anymoldprojTime{\timet}$,
$u \notin \outmoldprojTime{\timet}$ and the invariant is
preserved at time $\timet$.

Pebble Era while $\anymoldprojTime{\timet} \setminus
\pconf_\eta \ne \emptyset$, pick
any $u \in \anymoldprojTime{\timet} \setminus \pconf_\eta$, and
pebble $u$ in $\pebbling$
(increment $\eta \defeq \eta + 1$ and then set $\pconf_\eta \defeq
\pconf_{\eta - 1} \union \{ u \}$).
The invariant is preserved at time $\timet$.

At the end of the two sequences, $\outmoldprojTime{\timet+1} \subseteq
\anymoldprojTime{\timet+1} = \anymoldprojTime{\timet} = \pconf_\eta$, so
the invariant now holds also at time $\timet+1$.

We complete the proof of Item (2). For any visiting pebbling
$\pebbling'$ of $\mold(G)$, the corresponding pebbling $\pebbling$
is a visiting pebbling of $G$ by invariant (a), thus some
constructed configuration $\pconf_\eta$ has at least
$\visitprice{G}$ pebbles.

The configuration has been appended to
$\pebbling$ in case (III) above, and without loss of generality we
can assume it is either at the beginning of an “unpebble era” or
at the end of a “pebble era”, since the number of pebbles in
$\pconf_\eta$ decreases in the former and increases in the latter.

Since the beginning of an “unpebble era” other than the first is
also the end of a “pebble era”, we can furthermore assume the

This means that for some $\timet$ we have
$\anymoldprojTime{\timet} = \anymoldprojTime{\timet+1} =
\pconf_\eta$,

so either the corresponding configuration $\pconf_\timet'$
(when $v\outmold$ is unpebbled) or $\pconf_{\timet+1}'$ (when
$v\outmold$ is pebbled) has at least $\visitprice{G} + 2$ pebbles,
including $s$, $v\inmold$ and $v\outmold$. This completes
Item (2).

§.§ s

As an application of molding (Construction <ref>) we show
a construction that controls the visiting price of a node, and that
allows us to construct gadgets for the components of a quantified boolean

For any non-negative integer $\bank$ we define the
of toll $\bank$ from $a$ to $b$ (represented by
Fig. <ref>) as follows.

If $r=0$ then the just joins the vertices
$a$ and $b$ with an edge $(a,b)$.

If $r>0$ let $T_\bank$ be the graph having $\visitprice{T_\bank} =
\persistentprice{T_\bank} = \bank$ given by

The of toll $\bank$ from $a$ to $b$ is the graph
$\mold(T_\bank)$, identifying $a$ with the special
source $s$ in $\mold(T_\bank)$, and identifying $b$ with
the unique sink in $\mold(T_\bank)$.

of toll $\bank$ from $a$ to $b$.

Let $G$ be any graph that contains a of toll $\bank$ from $a$ to $b$.
Call the nodes $\tilde R \defeq \ancnode[G]{b} \setminus
\ancnode[G]{a}$ to be properly in the , and call the
nodes $R \defeq \tilde R \union \{ a \}$ to be in the .
The construction is sensitive to whether the pebble on node $a$ is
counted, whether the pebbling prices are restricted to $R$ or to
$\tilde R$.

We have $\persistentprice[R]{b} = \visitprice[R]{b} = \bank + 2$ and
$\persistentprice[\tilde R]{b} = \visitprice[\tilde R]{b} = \bank + 1$.

$\persistentprice[R]{b} \le \bank + 2$ and
$\persistentprice[\tilde R]{b} \le \bank + 1$
by (the proof of) Item (1) of lem:Molding (since pebbles
outside of $R$ or of $\tilde R$ are not counted), and $\visitprice[R]{b}
\ge \bank + 2$ and $\visitprice[\tilde R]{b} \ge \bank + 1$ by Item (2) of

The fact that $\persistentprice[R]{b}$ and $\persistentprice[\tilde R]{b}$ do not
differ by more than one holds not only for s but for any graph.

Consider regions $R_1$ and $R_2$ such that $R_1 = R_2 \setminus \{ s_2 \}$
for some source $s_2$ of $R_2$ ($\prednode{s_2} \intersect R_2 =
\emptyset$).
We have

\[
\begin{matrix}
\persistentprice[R_1]{v}
&\le& \persistentprice[R_2]{v}
&\le& \persistentprice[R_1]{v} + 1 \\
\visitprice[R_1]{v}
&\le& \visitprice[R_2]{v}
&\le& \visitprice[R_1]{v} + 1 \\
\surroundprice[R_1]{v}
&\le& \surroundprice[R_2]{v}
&\le& \surroundprice[R_1]{v} + 1 \enspace .
\end{matrix}
\]

§ PSPACE-COMPLETENESS

In this section we give all details of the construction in
th:pspace-construction, restated in the following theorem, and
its full proof.

Given a quantified $3$ $\QBF$,
there is a constructible graph $\gadgetConst{\QBF}$ and a computable number $\gamma(\QBF)$ such that
$\Persistentprice{\gadgetConst{\QBF}}=\gamma(\QBF)+\ib{\QBF \text{\
is \false}}$.

Let $ \variable_{1} \ldots \variable_{n}$ be the variables of $\QBF$.

We sort the variables from the innermost to the outermost quantifier
and denote by $\QBF_{i}$ the quantified $3$ with just the $i$
innermost quantifiers, namely $\QBF_{0}=\Land^{m}_{j=1} C_{j}$,
$Q \in \set{\forall, \exists}$, and $\QBF=\QBF_{n}$.

For each $\QBF_{i}$ we consider the gadget $\gadgetConst{\QBF_{i}}$,
where $\gadgetConst{\QBF_{0}}$ is built as defined in
Construction <ref> and each $\gadgetConst{\QBF_{i}}$ for
$i\in[n]$ is built according to either
Construction <ref> or
Construction <ref>, depending on the
$i\th$ innermost quantifier.

Furthermore we fix the sequence of integers $\{\gamma_{i}\}^{n}_{i=0}$
where $\gamma_{0} \defeq 2m+7$, $\gamma_{i} \defeq 3+\gamma_{(i-1)}$
if the $i\th$ innermost quantifier is existential, and
$\gamma_{i}=5+\gamma_{(i-1)}$ if the $i\th$ innermost quantifier
is universal.

To analyze the gadgets for the subformulas we need the next definition.

A region is an induced subgraph of the final gadget
$\gadgetConst{\QBF}$ (or of component gadgets as we build up the
final gadget).

We slightly abuse notation and refer to a region by
a subset of vertices; for example, given a subset of vertices $\Region$ of
a gadget $\gadget$, we use $\persistentprice[\Region]{\gadget}$,
$\visitprice[\Region]{\gadget}$ and $\surroundprice[\Region]{\gadget}$
to denote the different pebbling prices over the subgraph of $\gadget$ induced on

With these notations and definitions in place,
Theorem <ref> follows immediately from the
next lemma when $i$ is equal to $n$.

In this case $\partassign$ and $\Region$, as stated in the
lemma, are respectively the empty assignment and the full graph

In the proof of the lemma we refer to definitions, lemmas and
constructions that we will present in full details in the
coming subsections.

Fix an arbitrary $0\leq i\leq n$ and let

* $\partassign$ be an assignment to all but the first $i$

* $\canonical$ be the canonical set of $\partassign$ according
to Definition <ref>;

* $\Region$ be the subset of vertices of
$\gadgetConst{\QBF_{i}}$ defined as
$V(\gadgetConst{\QBF_{i}}) \setminus \ancnode{\canonical}$.

It holds that

\begin{equation}\label{eq:quantifierRecursion}
\Persistentprice[\Region]{\gadgetConst{\QBF_{i}}} =  \gamma_{i}
+\ib{\restrict{\QBF_{i}}{\partassign} \text{\ is \false}}\eqperiod
\end{equation}

When $i = 0$, the gadget $\gadgetConst{\QBF_0}$ is the CNF gadget
from Construction <ref> and the base case follows
immediately by lem:CNFGadget, where $\beta_{m}=2m$.

When $i>0$, consider the two possible extensions of $\partassign$ that
assign $\variable_{i}$, namely

$\partassign_{0} \defeq \partassign \cup \{\variable_{i}=0\}$
$\partassign_{1} \defeq \partassign \cup \{\variable_{i}=1\}$.

Consider also the corresponding canonical sets
$\canonical_{0}, \canonical_{1}$ and the regions
$\Region_{0} \defeq V(\gadgetConst{\QBF_{(i-1)}}) \setminus
\ancnode{\canonical_{0}}$
$\Region_{1} \defeq V(\gadgetConst{\QBF_{(i-1)}}) \setminus
\ancnode{\canonical_{1}}$. By induction it holds that

* $\Persistentprice[\Region_{0}]{\gadgetConst{\QBF_{(i-1)}}}=
\gamma_{(i-i)}+\ib{\partassign_{0} \text{\ falsifies\ } \QBF_{(i-1)}}$

* $\Persistentprice[\Region_{1}]{\gadgetConst{\QBF_{(i-1)}}}=
\gamma_{(i-1)}+\ib{\partassign_{1} \text{\ falsifies\ } \QBF_{(i-1)}}$

so the hypothesis of Lemmas <ref>
and <ref> holds.

When $\QBF_{i}=\forall\variable_{i}\QBF_{i-1}$ lem:UniversalQuantifierGadget gives that

\begin{equation}\label{eq:universalRecursion}
\Persistentprice{\gadgetConst{\QBF_{i}}}= 5+\gamma_{(i-i)}+
\ib{
\partassign_{0} \text{\ falsifies\ } \QBF_{(i-1)} \text{\ or\ }
\partassign_{1} \text{\ falsifies\ } \QBF_{(i-1)}},
\end{equation}

and $\QBF_{i}=\exists\variable_{i}\QBF_{(i-1)}$
lem:ExistentialQuantifierGadget gives that

\begin{equation}\label{eq:existentialRecursion}
\Persistentprice{\gadgetConst{\QBF_{i}}}= 3+\gamma_{(i-i)}+
\ib{
\partassign_{0} \text{\ falsifies\ } \QBF_{(i-1)} \text{\ and\ }
\partassign_{1} \text{\ falsifies\ } \QBF_{(i-1)}}\eqperiod
\end{equation}

Equations (<ref>)
and (<ref>) are equivalent, for the
respective quantifier type, to
Equation (<ref>).

§.§ Literal Gadget

lem:ChristmasTree allows us to create an edge $(u,v)$ with
$\persistentprice{v} = \persistentprice{u} + 1 = \bank + 1$ given any $\bank \in
\N^+$.
This is used for constructing gadgets for literals (represented as

[Literal Gadget]

Fix a literal $\literal$ and an integer $\bank \in \N^+$.
Let $T_\bank$ be the graph having $\visitprice{T_\bank} = \persistentprice{T_\bank}
= \bank$ given by lem:ChristmasTree.
The literal gadget of price $\bank$ for $\literal$, is denoted
as $\literalConst{\literal}{\bank}$.
To construct it, take a copy of $T_\bank$ and call its sink $\literal'$.
Then add a new node, named $\literal$ as the corresponding literal, and add the edge $(\literal', \literal)$.

Literal gadget of price $\bank$ for $\literal$.

In $\literalConst{\literal}{\bank}$, $\persistentprice{\literal} - 1 =
\persistentprice{\literal'} = \visitprice{\literal'} = \bank$.

Should we have a lemma “visit($G$)=surr($G^+$)”?
Note that visiting node $\literal'$ is equivalent to surrounding node
Hence $\persistentprice{\literal} - 1 = \surroundprice{\literal} = \visitprice{\literal'}
= \persistentprice{\literal'} = \bank$ by eq:surrounding-leq-visiting-leq-persistent, lem:surrounding-eq-persistent,
and lem:ChristmasTree.

It would be nice to have T/F/* or True/False/Undef.

We associate pebbling configurations on $\Literal \defeq
\literalConst{\bank}{\literal}$ with truth value , or (undefined) as follows.

Fix a literal gadget $\Literal \defeq \literalConst{\bank}{\literal}$.
Given a pebbling configuration $\pconf$, say
node $\literal'$ is  on
$\persistentprice[L]{\pconf}=\visitprice{\literal'} = \bank$ (when restricted to
that is, if the empty configuration cannot be reached without entering a
configuration which has $\bank$ pebbles.
Given a pebbling configuration on $\Literal$, say literal $\literal$ is in

*  position, if node $\literal$ has a pebble and node $\literal'$ is not

* position, if node $\literal'$ is ; and

* position, if node $\literal$ has no pebble and node $\literal'$ is not

A transition of literal $\literal$ is a change of position for
$\literal$ (from position to position, or from position to position) due to a pebble move.
Finally, we identify certain canonical positions with
configurations on $\Literal$ as follows:

* the canonical position is the configuration where only node
$\literal$ has a pebble;

* the canonical position is the configuration where only node
$\literal'$ has a pebble; and

* the canonical position is the empty configuration.

Clearly, the canonical position (resp. canonical position,
canonical position) is indeed a position (resp. position, position).

Fix a literal gadget $\Literal \defeq \literalConst{\bank}{\literal}$.

* it is impossible to transition directly from position to
position, and vice versa; and

* at a transition, there are $\bank$ pebbles on

Note that node $\literal'$ is on any configuration with a pebble on
node $\literal'$.
To change from position to position, node $\literal$ needs to
be pebbled, and hence node $\literal'$ must have a pebble at some time.
At that time, node $\literal'$ is , so the configuration is in
This gives Item (1).

Hence the only valid transitions are from position to position (or its reverse), and from position to position (or
its reverse).
In any of these, node $\literal'$ needs to switch between locked and
unlocked status, which requires a configuration with $\bank$ pebbles on
$\ancnode[\Literal]{\literal'}$ by definition of .
This gives Item (2).

§.§ Variable Gadget

Let $\bank_i \in \N^+$ be an integer to be specified later, which is
associated with the $i\th$ variable $\variable_i$.

Inspired by previous works <cit.>
truth values are represented using the gadget in fig:Variable.
[Variable Gadget]

For the variable $\variable_i$, its variable gadget
$\gadgetConst{\variable_i}$ is constructed as the disjoint union two
literal gadgets of price $\bank_i$, one for literal $\variable_i$ and one
for literal $\bar\variable_i$.

Variable $\variable_i$.

For the gadget $\gadget \defeq \gadgetConst{\variable_i}$, its nodes are
$V(\gadget) \defeq \Ancnode[\gadget]{ \{ \variable_i, \bar\variable_i \} }$.

Fix a variable gadget $\gadget \defeq \gadgetConst{\variable_i}$
consisting of literal gadgets $\Literal_1 \defeq
\literalConst{\bank_i}{\variable_i}$ and
$\Literal_0 \defeq \literalConst{\bank_i}{\bar\variable_i}$.
We identify certain canonical positions with configurations on
$\gadget$ as follows:

* the canonical position is the configuration where only nodes
$\variable_i$ and $\bar\variable_{i}'$ have pebbles;

* the canonical position is the configuration where only
nodes $\variable_i'$ and $\bar\variable_{i}$ have pebbles; and

* the canonical position is the empty configuration.

Variable $\variable_i$ can be put into one among canonical and canonical positions using at most $ \bank_{i}+1 $

To put variable $\variable_i$ in canonical position, persistently
pebble node $\variable_i$, then persistently pebble $\bar\variable_i'$.
It can be done with $\bank_i + 1$ pebbles by lem:LiteralGadget.
A symmetric argument shows that $\variable_i$ can be put in canonical
position with $\bank_i + 1$ pebbles.

As we will see in later sections, the design of the quantifier gadgets would
ensure that any pebbling strategy would effectively associate truth value
via the canonical positions.
This motivates the following definition.

Given a partial assignment $ \funcdescr{\partassign}{[n]}{\{ \true,
\false, \tvundef \}} $,
the canonical nodes of variable $\variable_i$ under $\partassign$ are

* $\{ \variable_i, \bar\variable_i' \}$ if $\partassign(i) = \true$;

* $\{ \variable_i', \bar\variable_i \}$ if $\partassign(i) =
\false$; and

* $\{\}$ if $\partassign(i) = \tvundef$.

Note that if $\partassign(i) \ne \tvundef$, then there are two pebbles on the
ancestors of the canonical nodes of $\variable_i$.
For example, if $\partassign(i) = \true$, then there is a pebble on
$\ancnode{\variable_i}$ and a pebble on $\ancnode{\bar\variable_i'}$.

In general, we consider a partial assignment on variables
$ \funcdescr{\partassign}{[n]}{\{ \true, \false, \tvundef \}} $
as a partial assignment on literals:

* if variable $\variable_i$ is assigned under $\partassign$
($\partassign(i) = \true$), then literal $\variable_i$ is assigned
and literal $\bar\variable_i$ is assigned ;

* if variable $\variable_i$ is assigned under $\partassign$
($\partassign(i) = \false$), then literal $\variable_i$ is assigned
and literal $\bar\variable_i$ is assigned ;

* if variable $\variable_i$ undefined under $\partassign$
($\partassign(i) = \tvundef$), then literal $\variable_i$ is and literal $\bar\variable_i$ is .

As we will argue later, the design of the quantifier gadgets would ensure
that “invalid variable assignments” would not be a problem:
for example,
the two literals of the same variable cannot be put into the position
at the same time (cla:Clearance); also,
it does not help to put the two literals of the same variable into the
position at the same time, and
each variable will be assigned eventually (lem:ExistentialLowerBound

The canonical nodes (of a partial assignment) are useful for defining
certain regions over different component gadgets in the overall

§.§ Clause Gadget

Let $\beta_j \ge 2$ be an integer to be specified later, which is
associated with the $j\th$ clause $\clause_j$.

The gadget for the $j\th$ clause, $\clause_j = \literal_{j,1} \lor
\literal_{j,2} \lor \literal_{j,3}$, uses as a component the gadget which is described in Construction <ref>.

Its skeleton is shown in
fig:Clause (the literal gadgets are simplified in fig:Clause
for a cleaner diagram).

Assume that the literals $\literal_{j,1}, \literal_{j,2}, \literal_{j,3}$
are over distinct variables.

[Clause Gadget]

Assume that for each variable $\variable_i$, $1 \le i \le n$ we have
the corresponding variable gadget $\gadgetConst{\variable_i}$, two
literal gadgets for $ \variable_{i} $ and $ \bar\variable_{i} $.

For the $j\th$ clause $\clause_j$, its clause gadget
$\gadgetConst{\clause_j}$ is constructed as follows.
Create nodes $a_j, b_j, c_j, u_j, v_j, p_j$, and edges

\begin{equation}
(a_j, u_j), (b_j,u_j), (b_j, v_j), (c_j, v_j), (u_j, p_j), (v_j,
\end{equation}

Finally, add three s of toll $\beta_j$, from $\literal_{j,1}$ to
$a_j$, from $\literal_{j,2}$ to $b_j$, and from $\literal_{j,3}$ to $c_j$
(where the nodes $\literal_{j,1}, \literal_{j,2}, \literal_{j,3}$
are the ones from the corresponding literal gadgets).

Note that in fig:Clause the six nodes $\literal_{j,1}$,
$\literal_{j,1}'$, $\literal_{j,2}$, $\literal_{j,2}'$, $\literal_{j,3}$,
and $\literal_{j,3}'$ come from the variable gadgets corresponding to the
variables in literals $\literal_{j,1}$, $\literal_{j,2}$ and
Recall the definitions of canonical nodes in
For example, if literal $\literal_{j,1}$ is in position, literals
$\literal_{j,2}, \literal_{j,3}$ position, then their canonical nodes
are $\literal_{j,1}, \literal_{j,2}', \literal_{j,3}'$.

Clause $j$.

In this subsection, focus on the gadget $\gadget \defeq
\gadgetConst{\clause_j}$ constructed for the $j\th$ clause $\clause_j$.
The gadget $\gadget$ behaves like a disjunction in the sense that at least
one literal is assigned if, and only if, $\beta_j + 3$ additional
pebbles are needed to surround $p_j$.

Fix a partial assignment $\partassign$.
Assume none of the literals $\literal_{j,1}, \literal_{j,2},
\literal_{j,3}$ is assigned , and at least one of them is assigned
Let $\canonical_j$ be their canonical nodes.
Consider the region $R_j \defeq \ancnode[\gadget]{p_j} \setminus
\ancnode[\gadget]{\canonical_j}$ beyond the canonical nodes.
Then $\surroundprice[R_j]{p_j} \le \beta_j + 3$.

Note that the $j\th$ clause gadget is symmetric in the three literals
$\literal_{j,1}, \literal_{j,2}, \literal_{j,3}$ when restricting
attention to

$\Ancnode[\gadget]{\{ a_j, b_j, c_j \}}
\setminus
\Pancnode[\gadget]{\{\literal_{j,1}', \literal_{j,2}',
\literal_{j,3}'\}}$.

If at least one of the literals $\literal_{j,1}, \literal_{j,2},
\literal_{j,3}$ is assigned , we claim that it takes at most
$\beta_j + 3$ pebbles over $R_j$ to leave pebbles only on $\{ a_j, b_j, c_j
\}$;
afterwards $p_j$ can be surrounded by pebbling $u_j$ and $v_j$ (note that
$\beta_j + 3 \ge \underbrace2_{u_j, v_j} + \underbrace3_{a_j, b_j, c_j} =

To prove the claim, note that if $\literal_{j,1}$ is assigned , then
the intersection of $R_j$ with the from $\literal_{j,1}$ to $a_j$
is precisely the nodes properly in the ;
if $\literal_{j,1}$ is assigned , then the intersection is precisely
the nodes in the . This holds similarly for literals $
\literal_{j,2} $ and $ \literal_{j,3} $.

By symmetry over
$\Ancnode[\gadget]{\{ a_j, b_j, c_j \}}
\setminus
\Pancnode[\gadget]{\{\literal_{j,1}', \literal_{j,2}',
\literal_{j,3}'\}}$,
$\literal_{j,1}$ is assigned , and each of $\literal_{j,2}$,
$\literal_{j,3}$ is assigned or .
Consider the following strategy to place three pebbles on $\{ a_j, b_j, c_j \}$,
where pebbles outside of $R_j$ are not counted:

* Persistently pebble the from $\literal_{j,2}$ to $b_j$.
It takes at most $\beta_j + 2$ pebbles over $R_j$ by

* Persistently pebble the from $\literal_{j,3}$ to $c_j$.
Now only $b_j$ and $c_j$ have pebbles over $R_j$.
It takes at most $\underbrace{\beta_j + 2}_{\ancnode{c_j}} +
\underbrace{\vphantom{\beta_j}1}_{b_j} = \beta_j + 3$ pebbles over $R_j$ by

* Persistently pebble the from $\literal_{j,1}$ to $a_j$.
Since $\literal_{j,1}$ is outside of $R_j$, it takes at most $\beta_j
+ 1$ pebbles over the intersection of the and $R_j$ by
lem:Highway, for a total of $\underbrace{\beta_j +
1}_{\ancnode{a_j}} + \underbrace{\vphantom{\beta_j}2}_{b_j,c_j} = \beta_j + 3$
Now $a_j$, $b_j$ and $c_j$ have pebbles.

Fix a partial assignment $\partassign$.
Assume all of the literals $\literal_{j,1}$, $\literal_{j,2}$ and
$\literal_{j,3}$ are assigned .

$\canonical_j \defeq \{ \literal_{j,1}', \literal_{j,2}',
\literal_{j,3}' \}$  be their canonical nodes.

Consider the region $R_j \defeq \ancnode[\gadget]{p_j} \setminus
\ancnode[\gadget]{\canonical_j}$ beyond the canonical nodes.
Then $\surroundprice[R_j]{p_j} \ge \beta_j + 4$.

Note that $\gadget$ consists of a pyramid whose sources are attached to three
Since all literals are assigned , the intersection of $R_j$ with
each of the is precisely the nodes in the .

Fix an induced subgraph $F \subseteq \gadget$ ($F =$ the from
$\literal_{j,1}$ to $a_j$) having a unique sink.
Say a pebbling configuration on $F$ is  if
$\persistentprice[F]{\pconf}=\visitprice{F}$, that is if
in order to reach the empty configuration it is necessary to pass
through a configuration with $\visitprice{F}$ pebbles.

In particular, any configuration with a pebble on the sink of $F$ is
on $F$.

Also, if a configuration is on $F$, then there is a pebble on $F$.
Given a pebbling configuration on $\gadget$, say $a_j$ (resp. $b_j$,
$c_j$) is if the configuration is on the from
$\literal_{j,1}$ to $a_j$ (resp. from $\literal_{j,2}$ to $b_j$, from
$\literal_{j,3}$ to $ c_{j} $).

With locking in mind, consider a “projected” configuration on the
pyramid defined as follows.
Given a pebbling configuration $\pconf$ on $\gadget$, its projection to the
pyramid is $\projection{\pconf}
\defeq \bigl( \{ u_j, v_j, p_j \} \intersect \pconf \bigr)
\union \bigl\{ t \in \{ a_j, b_j, c_j \} \where t\text{ is \vislocked under }\pconf
\bigr\}$.
Note that given a strategy on $\gadget$, its (configuration-wise)
projection to the pyramid is a legal strategy on the pyramid.

We are interested in the truncated paths $\breve\pi$ on the pyramid (source to sink paths excluding the sink, which are in bijection to the
edges $(a_j, u_j)$, $(b_j, u_j)$, $(b_j, v_j)$, $(c_j, v_j)$), and in
particular whether they are blocked under $\projection{\pconf}$.
A truncated path $\breve\pi$ is blocked under $\projection{\pconf}$ if
$\breve\pi \intersect \projection{\pconf} \ne \emptyset$.

Consider a strategy on $\gadget$ to surround $p_j$.
Its projection to the pyramid is a strategy on the pyramid to surround
At the beginning, all truncated paths on the pyramid are not blocked;
at the end, all truncated paths are blocked.
Consider the first time that all truncated paths on the pyramid are
in the strategy projected on the pyramid, this must be the result of
pebbling a source node $a_j$, $b_j$, or $c_j$.
By symmetry (in the rest of this argument), assume $a_j$ is pebbled, then
there are at least two more pebbles on the pyramid in the projected
Since $a_j$ is being pebbled in the projected strategy, $a_j$ is getting
on $\gadget$ (restricting attention to the from
$\literal_{j,1}$ to $a_j$, there are as many pebbles as the visiting
price of the ), accounting for $\beta_j + 2$ pebbles in the
intersection of $R_j$ and the to $a_j$ by lem:Highway.
The two other pebbles in the projected strategy each account for one more
pebble over $R_j$, for a total of $\beta_j + 4$ pebbles.

The lower bound shown in lem:FalseClause holds for
clauses which are falsified. We now prove a weaker lower bound on
the surrounding price for the satisfied clauses, which matches the
upper bound.

Fix a partial assignment $\partassign$.
Assume none of literals $\literal_{j,1}$, $\literal_{j,2}$, or
$\literal_{j,3}$ is assigned .
Let $\canonical_j$ be their canonical nodes.
Consider the region $R_j \defeq \ancnode[\gadget]{p_j} \setminus
\ancnode[\gadget]{\canonical_j}$ beyond the canonical nodes.
Then $\surroundprice[R_j]{p_j} \ge \beta_j + 3$.

Follow the proof of lem:FalseClause to define , projection
to the pyramid, truncated paths on the pyramid, and blocking on the
The only difference is that, since some literal can be assigned ,
the intersection of $R_j$ with some of the can be the nodes
properly in the .

Consider a strategy on $\gadget$ to surround $p_j$.
Its projection to the pyramid is a strategy on the pyramid to surround
As in the proof of lem:FalseClause, consider the first time that
all truncated paths on the pyramid are blocked, which in the projected
strategy must be the result of pebbling a source node, say, $a_j$.
And there are at least two more pebbles on the pyramid in the projected
Since $a_j$ is being pebbled in the projected strategy, $a_j$ is getting
on $\gadget$ (restricting attention to the from
$\literal_{j,1}$ to $a_j$, there are as many pebbles as the visiting
price of the ), accounting for $\beta_j + 1$ pebbles in the
intersection of $R_j$ and the to $a_j$ by lem:Highway (note
that node $\literal_{j,1}$ may be outside of $R_j$ if literal
$\literal_{j,1}$ is in position).
The two other pebbles in the projected strategy each account for one more
pebble over $R_j$, for a total of $\beta_j + 3$ pebbles.

Assuming that the literal gadgets are in the position corresponding
to $ \partassign $, we represent “whether $\partassign$ falsifies
$\clause_j$” through an increase in the persistent price of the sink
of the corresponding gadget,

if $\partassign$ satisfies $\clause_j$, then the persistent
price would be a certain number ($\beta_j + 4$);
if $\partassign$ falsifies $\clause_j$, then the persistent price
would be one plus that number ($\beta_j + 5$).

The difference in pebbling prices can be succintly expressed using
the Iverson bracket notation $\ibleft \partassign \text{ falsifies
}\clause_j \ibright$.

Fix a partial assignment $\partassign$.
Assume none of literals $\literal_{j,1}$, $\literal_{j,2}$, or
$\literal_{j,3}$ is assigned .
Let $\canonical_j$ be their canonical nodes.
Consider the region $R_j \defeq \ancnode[\gadget]{p_j} \setminus
\ancnode[\gadget]{\canonical_j}$ beyond the canonical nodes.
$\persistentprice[R_j]{p_j} =
\beta_j + 4 +
\ibleft
\partassign \text{\ falsifies\ }\clause_j \ibright$.

If $\partassign$ satisfies $\clause_j$, at least one literal is
assigned , then $\persistentprice[R_j]{p_j} = \beta_j + 4$ because
persistent price is one plus surrounding price
(lem:surrounding-eq-persistent), and the upper bound
(lem:TrueClause) matches the lower bound (lem:AnyClause).
If $\partassign$ falsifies $\clause_j$, all literals are assigned
, then $\persistentprice[R_j]{p_j} = \beta_j + 5$ because it has to
increase (lem:FalseClause) but not by more than one

§.§ Conjunction Gadget

To construct a gadget for the conjunction of $m$ clauses, it suffices to
repeatedly compose a gadget for the conjunction two smaller gadgets, using
the conjunction gadget represented in fig:GadgetConjunction.

[Conjunction Gadget]

Assume two gadgets $G_1$ and $G_2$ with unique sinks are constructed.
Construct the conjunction gadget of weight $\bank$ of $G_1$ and
$G_2$, denoted $\conjConst{\bank}{G_1}{G_2}$, as follows.
Call $\sink_1$ the sink of $G_1$, $\sink_2$ the sink of $G_2$.
Construct nodes $d_1$, $d_2$, $d_3$, $d_4$, $e$, and edges $(d_1, d_3)$,
$(d_2, d_3)$, $(d_4, e)$.
Add a of toll $\bank$ from $\sink_1$ to $d_1$, a of toll
$\bank-1$ from $\sink_2$ to $d_2$, and a of toll $\bank-2$ from
$d_3$ to $d_4$.

centerminimum size=1.2cm

Conjunction gadget of weight $\bank$ of $G_1$ and $G_2$.

For the gadget $G \defeq \conjConst{\bank}{G_1}{G_2}$, the nodes in the
gadget are $V(G) = \ancnode{e} \setminus \bigl( \propancnode{\sink_1} \union
\propancnode{\sink_2} \bigr)$.
We want to analyze pebbling prices restricted to a certain region $\Region$
(in the final gadget containing the conjunction gadgets) which will be a
superset of the nodes of $G$.

Fix a region $\Region$ where $\Region \supseteq V(G)$.
If $\persistentprice[\Region]{\sink_1} \le \bank + 1$ and
$\persistentprice[\Region]{\sink_2} \le \bank$, then
$\surroundprice[\Region]{e} \le \bank + 2$.

Consider the following strategy to visit $d_4$ (equivalently, surround
$e$) using at most $\bank+2$ pebbles: