When Input Integers are Given in the Unary
Numeral Representation111This is a preliminary report of the current work,
which has appeared in the Proceedings of the 24th Italian Conference on
Theoretical Computer Science (ICTCS 2023), Palermo, Italy, September 13–15,
2023, CEUR Workshop Proceedings (CEUR-WS.org).

Tomoyuki Yamakami222Present Affiliation: Faculty of Engineering, University of
Fukui, 3-9-1 Bunkyo, Fukui 910-8507, Japan

###### Abstract

Many $\mathrm{NP}$-complete problems take integers as part of their input
instances. These input integers are generally binarized, that is, provided in
the form of the “binary” numeral representation, and the lengths of such
binary forms are used as a basis unit to measure the computational complexity
of the problems. In sharp contrast, the “unarization” (or the “unary” numeral
representation) of numbers has been known to bring a remarkably different
effect onto the computational complexity of the problems. When no
computational-complexity difference is observed between binarization and
unarization of instances, on the contrary, the problems are said to be strong
NP-complete. This work attempts to spotlight an issue of how the unarization
of instances affects the computational complexity of various combinatorial
problems. We present numerous NP-complete (or even NP-hard) problems, which
turn out to be easily solvable when input integers are represented in unary.
We then discuss the computational complexities of such problems when taking
unary-form integer inputs. We hope that a list of such problems signifies the
structural differences between strong NP-completeness and non-strong NP-
completeness.

Keywords. unary numeral representation, unarization of integers, logarithmic-
space computation, pushdown automata, log-space reduction

##  1 Background and Quick Overview

###  1.1 Unary Representations of Integer Inputs

The _theory of NP-completeness_ has made great success in providing a
plausible evidence to the hardness of target computational problems when one
tries to solve them in feasible time. The proof of $\mathrm{NP}$-completeness
of those problems therefore makes us turn away from solving them in a
practical way but it rather guides us to look into the development of
approximation or randomized algorithms.

In computational complexity theory, we often attempt to determine the minimum
amount of computational resources necessary to solve target combinatorial
problems. Such computational resources are measured in terms of the sizes of
input instances given to the problems. Many $\mathrm{NP}$-complete problems,
such as the _knapsack problem_ , the _subset sum problem_ , and the _integer
linear programming problem_ , concern the values of integers and require
various integer manipulations. When instances contain integers, these integers
are usually expressed in the form of “binary” representation. Thus, the
computational complexities, such as running time or memory space, are measured
with respect to the total number of bits used for this representation.

This fact naturally brings us a question of what consequences are drawn when
input integers are all provided in “unary” using the unary numeral system
instead. How does the unary representation affects the computational
complexity of the problems? In comparison to the binary numeral system, the
unary numeral system is so distinctive, that we need to heed a special
attention in our study on the computational complexity of algorithms.

When input integers given to combinatorial problems are expressed in unary, a
simple transformation of the unary expression of input integers to their
binary representations makes the original input lengths look exponentially
larger than their binary lengths. Thus, any algorithm working with the
unarized integer inputs seem to consume exponentially less time than the same
algorithm with binarized integer inputs. This turns out to be a quite short-
sighted analysis.

We often observe that the use of the unary representation significantly alters
the computational complexity of combinatorial problems. However, a number of
problems are known to remain $\mathrm{NP}$-complete even after we switch
binarized integer inputs to their corresponding unarized ones (see [5, Section
4.2]). Those problems are said to be _strong NP-complete_ 333Originally, the
strong $\mathrm{NP}$-completeness has been studied in the case where all input
integers are _polynomially bounded_. This case is essentially equivalent to
the case where all input integers are given in unary. See a discussion in,
e.g., [5, Section 4.2]. and this notion has been used to support a certain
aspect of the robustness of $\mathrm{NP}$-completeness notion. Non-strong
$\mathrm{NP}$-complete problems are, by definition, quite susceptible to the
change of numeral representations of their input integers between the binary
representation and the unary representation. It is therefore imperative to
study a structural-complexity aspect of those non-strong
$\mathrm{NP}$-complete problems when input integers are provided in the form
of the unary numeral representation. In this work, we wish to look into the
features of such non-strong $\mathrm{NP}$-complete problems.

Earlier, Cook [4] discussed the computational complexity of a unary-
representation analogue of the knapsack problem, called the _unary 0-1
knapsack problem_ (UK), which asks whether or not there is a subset of given
positive integers, represented in unary, whose sum matches a given target
positive integer. This problem UK naturally falls in $\mathrm{NL}$
(nondeterministic logarithmic space) but he conjectured that UK may not be
$\mathrm{NL}$-complete. This conjecture is supported by the fact that even an
appropriately designed one-way one-turn nondeterministic counter automaton can
recognize $\mathrm{UK}$ (e.g., [1]). Jenner [7] introduced a variant of UK
whose input integers are given in a “shift-unary” representation, where a
_shift-unary representation_ $[1^{a},1^{b}]$ represents the number $a\cdot
2^{b}$. She then demonstrated that this variant is actually
$\mathrm{NL}$-complete. We further expand such a shift-unary representation to
a _multiple shift-unary representation_ by allowing a finite series of
positive integers and to a _general unary (numeral) representation_ by taking
all possible integers, including zero and negative ones. See Section 2.1 for
their precise definitions.

Driven by our great interest in the effect of the unarization of inputs,
throughout this work, we wish to study the computational complexity of
combinatorial problems whose input integers are in part unarized by the unary
representation.

For the succinctness of further descriptions, we hereafter refer to input
integers expressed in the unary numeral system as _unary-form integers_ (or
more succinctly, _unarized integers_) in comparison to _binary-form integers_
(or _binarized integers_).

###  1.2 New Challenges and Main Contributions

A simple pre-processing of converting a given unary-form input integer into
its binary representation provides obvious complexity upper bounds for target
combinatorial problems but it does not seem to be sufficient to determine
their precise computational complexity.

Our goal is to explore this line of study in order to clarify the roles of the
binary-to-unary transformation in the theory of $\mathrm{NP}$-completeness
(and beyond it) and cultivate a vast research area incurred by the use of
unary-form integers. In particular, we plan to focus on several non-strong
$\mathrm{NP}$-complete (or even NP-hard) problems and study how their
computational complexities can change when we replace the binary-form input
integers to the unary-form ones. Among various types of combinatorial problems
taking integer inputs, we look into number problems, graph-related problems,
and lattice-related problems. It is desirable for us to determine the precise
complexity of each combinatorial problem whose instances are unarized.

A brief summary of our results are illustrated in Figure 1. The detailed
explanation of the combinatorial problems and complexity classes listed in
this figure will be provided in Sections 2–5. We remark that the underlying
machines used to define those complexity classes are all limited to run in
polynomial time.

Figure 1: Inclusion relationships among complexity classes with solid lines
and membership relations of numerous decision problems listed in small boxes
to specific complexity classes.

##  2 Basic Notions and Notation

###  2.1 Numbers, Sets, Languages

We assume that all _polynomials_ have nonnegative integer coefficients. All
_logarithms_ are always taken to the base $2$. The notations $\mathbb{Z}$ and
$\mathbb{N}$ denote respectively the set of all integers and that of all
nonnegative integers. We further define $\mathbb{N}^{+}$ to be
$\mathbb{N}-\\{0\\}$. As a succinct notation, we use $[m,n]_{\mathbb{Z}}$ to
denote the _integer interval_ $\\{m,m+1,\ldots,n\\}$ for two integers $m$ and
$n$ with $m\leq n$. In particular, $[1,n]_{\mathbb{Z}}$ is abbreviated as
$[n]$ whenever $n\geq 1$. Given $n\in\mathbb{N}^{+}$, we define the linear
order $<_{[n]}$ on the set $[n]\times[n]$ as:
$(i_{1},i_{2})<_{[n]}(i_{2},j_{2})$ iff either $i_{1}<i_{2}$ or
$i_{1}=i_{2}\wedge j_{1}<j_{2}$. Moreover, $\mathbb{R}$ denotes the set of all
real numbers. Given a vector $x=(x_{1},x_{2},\ldots,x_{n})$ in
$\mathbb{R}^{n}$, the _Euclidean norm_ $\|x\|_{2}$ of $x$ is given by
$(\sum_{i\in[n]}x_{i}^{2})^{1/2}$ and the _max norm_ $\|x\|_{\infty}$ is done
by $\max\\{|x_{i}|:i\in[n]\\}$, where $|\cdot|$ indicates the absolute value.
Given a set $A$, ${\cal P}(A)$ denotes the _power set_ of $A$.

Conventionally, we freely identify decision problems with their associated
languages. We write $1^{*}$ (as a regular expression) for the set of strings
of the form $1^{n}$ for any $n\in\mathbb{N}$. For convenience, we define
$1^{0}$ to be the _empty string_ $\varepsilon$. Let $1^{+}$ denote the set
$1^{*}-\\{\varepsilon\\}$. Similarly, we use the notation $0^{*}$ for
$\\{0^{n}\mid n\in\mathbb{N}\\}$ with $0^{0}=\varepsilon$.

Given a positive integer $a$, the _unary representation_ of $a$ is of the form
$1^{a}$ (viewed as a string) compared to its binary representation. Notice
that the length of $1^{a}$ is exactly $a$ rather than $O(\log(a+1))$, which is
the length of the binary representation of $a$. A finite series
$(a_{1},a_{2},\ldots,a_{n})$ of positive integers is expressed by the
_multiple unary representation_ of the form
$(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$. When such an instance
$x=(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$ is given to a machine, we
explicitly assume that $x$ has the form of
$1^{a_{1}}\\#1^{a_{2}}\\#\cdots\\#1^{a_{n}}$ with a designated separator
symbol $\\#$. For a series of such instances $x=(x_{1},x_{2},\ldots,x_{m})$
with $x_{i}=(1^{a_{i1}},1^{a_{i2}},\ldots,1^{a_{in_{i}}})$ for $i\in[m]$ and
$n_{i}\in\mathbb{N}^{+}$, we further assume that $x$ takes the form of
$1^{a_{11}}\\#1^{a_{12}}\\#\cdots\\#1^{a_{1n_{1}}}\\#\\#1^{a_{21}}\\#1^{a_{22}}\\#\cdots\\#1^{a_{2n_{2}}}\\#\\#\cdots\\#\\#1^{a_{m1}}\\#1^{a_{m2}}\\#\cdots\\#1^{a_{mn_{m}}}$.
Moreover, for any positive integer of the form $a=p\cdot 2^{t}$ for
nonnegative integers $p$ and $t$, a _shift-unary representation_ 444Unlike the
unary and binary representations, a positive integer in general has more than
one shift-unary representation. In most applications, the choice of such
representations does not significantly affect the computational resources of
running machines. of $a$ is a pair $[1^{p},1^{t}]$, which is different from
the unary representation $1^{a}$ of $a$. The length of $[1^{p},1^{t}]$ is
$O(p+t)$ but not $a$. We also use a _multiple shift-unary representation_ ,
which has the form
$[[1^{a_{1}},1^{b_{1}}],[1^{a_{2}},1^{b_{2}}],\ldots,[1^{a_{n}},1^{b_{n}}]]$
with the condition that $2^{b_{i+1}}>a_{i}2^{b_{i}}$ for all $i\in[n-1]$. This
form represents the number $\sum_{i=1}^{n}a_{i}\cdot 2^{b_{i}}$. We intend to
call an input integer by the name of its representation. For this purpose, we
call the expression $1^{a}$ and $[1^{p},1^{t}]$ the _unary-form (positive)
integer_ (or more succinctly, the _unarized (positive) integer_) and the
_shift-unary-form (positive) integer_ , respectively.

To deal with “general” integers, including zero and negative integers,
however, we intend to express such an integer $a$ as a unary string by
applying the following special encoding function $\langle\cdot\rangle$. Let
$\langle a\rangle=1$ if $a=0$; $\langle a\rangle=2a$ if $a>0$; and $\langle
a\rangle=2|a|+1$ if $a<0$. We define the _general unary (numeral)
representation_ of $a$ as $1^{\langle a\rangle}$. In a similar way, a _general
shift-unary representation_ of $-a$ for $a>0$ is defined as a pair of the form
$[1^{\langle-p\rangle},1^{\langle t\rangle}]$, where $p$ and $t$ in
$\mathbb{N}$ must satisfy $a=p\cdot 2^{t}$.

###  2.2 Turing Machines and Log-Space Reductions

Our interest mostly lies on space-bounded computation. As a basic machine
model, we thus use deterministic/nondeterministic Turing machines (or
DTMs/NTMs, for short), each of which is equipped with a read-only input tape,
a rewritable work tape, and (possibly) a write-once555A tape is called _write-
once_ if its tape head never moves to the left and, whenever it writes a non-
blank symbol, it must move to the next blank cell. output tape.

The notation $\mathrm{L}$ (resp., $\mathrm{NL}$) denotes the collection of all
decision problems solvable on DTMs (resp., NTMs) in polynomial time using
logarithmic space (or log space, for short). A function $f$ from $\Sigma^{*}$
to $\Gamma^{*}$ for two alphabets $\Sigma$ and $\Gamma$ is _computable in log
space_ if there is a DTM such that, on input $x$, it produces $f(x)$ on a
write-once output tape in $|x|^{O(1)}$ time and $O(\log|x|)$ space. The
notation $\mathrm{FL}$ refers to the class of all such functions.

Let $L_{1}$ and $L_{2}$ denote two arbitrary languages. We say that $L_{1}$ is
_$\mathrm{L}$ -m-reducible to $L_{2}$_ (denoted
$L_{1}\leq^{\mathrm{L}}_{m}L_{2}$) if there exists a function $f$ (called a
reduction function) in $\mathrm{FL}$ such that, for any $x$, $x\in L_{1}$ iff
$f(x)\in L_{2}$. Given a language family ${\cal F}$, the notation
$\mathrm{LOG}({\cal F})$ denotes the family of all languages that are
$\mathrm{L}$-m-reducible to appropriately chosen languages in ${\cal F}$. We
further say that $L_{1}$ is _$\mathrm{L}$ -tt-reducible to $L_{2}$_ (denoted
$L_{1}\leq^{\mathrm{L}}_{tt}L_{2}$) if there are a reduction function
$f\in\mathrm{FL}$ and a truth-table $E:\\{0,1\\}^{*}\to\\{0,1\\}$ in
$\mathrm{FL}$ such that, for any string $x$, (i) $x\in L_{1}$ iff
$f(x)=(y_{1},y_{2},\ldots,y_{m})$ with $y_{i}\in\Sigma^{*}$ for any index
$i\in[m]$ and (ii) $E(L_{2}(y_{1}),L_{2}(y_{2}),\ldots,L_{2}(y_{m}))=1$, where
$L_{2}(y)=1$ if $y\in L_{2}$ and $L_{2}(y)=0$ otherwise.

Before solving a given problem on an input
$(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$ of unary-form numbers, it is often
useful to sort all entries $(a_{1},a_{2},\ldots,a_{n})$ of this input. Let us
define the function $f_{order}$ making the following behavior: on input of the
form $(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$ with
$a_{1},a_{2},\ldots,a_{n}\in\mathbb{N}^{+}$, $f_{order}$ produces a tuple
$(1^{a_{i_{1}}},1^{a_{i_{2}}},\ldots,1^{a_{i_{n}}})$ such that (1)
$a_{i_{1}}\geq a_{i_{2}}\geq\cdots\geq a_{i_{n}}$ and (2) if
$a_{i_{j}}=a_{i_{k}}$ with $i_{j}\neq i_{k}$, then $i_{j}<i_{k}$ holds.
Condition (2) is a useful property for one-way finite automata.

There is an occasion where, for a set of shift-unary-form integers
$[1^{p_{1}},1^{t_{1}}],[1^{p_{2}},1^{t_{2}}],\ldots,[1^{p_{n}},1^{t_{n}}]$, we
wish to compute the sum $s=\sum_{i=1}^{n}p_{1}\cdot 2^{t_{i}}$ and output the
binary representation of $s$ in the reverse order. The notation $f_{sum}$
denotes the function that computes this value $s$. The following lemma is
useful.

###### Lemma 2.1

The functions $f_{order}$ and $f_{sum}$ are both in $\mathrm{FL}$.

Those functions will be implicitly used for free when solving combinatorial
problems in the subsequent sections.

###  2.3 Multi-Counter Pushdown Automata

A _one-way determinsitic/nondeterminitic pushdown automaton_ (or a
1dpda/1npda, for short) is another computational model with a read-once input
tape and a standard (pushdown) stack whose operations are restricted to the
topmost cell. A _counter_ is a FILO (first in, last out) memory device that
behaves like a stack but its alphabet consists only of a “single” symbol, say,
$1$ except for the bottom marker $\bot$. A _one-way nondeterministic
$k$-counter automaton_ (or a $k$-counter 1ncta) is a one-way nondeterministic
finite automaton (1nfa) equipped with $k$ counters. We write
$\mathrm{1N}k\mathrm{CA}$ to denote the family of all languages recognized by
appropriate $k$-counter 1ncta’s running in polynomial time. We further expand
$\mathrm{1N}k\mathrm{CA}$ to $\mathrm{1NPD}k\mathrm{CA}$ by supplementing $k$
counters to 1npda’s. These specific machines are called _one-way
nondeterministic $k$-counter pushdown automata_ (or 1npdcta’s). When tape
heads of multi-counter automata and pushdown automata are allowed to move in
all directions, we call such polynomial-time machines by 2ncta’s and
2npdcta’s, respectively. With the use of these 2ncta’s and 2npdcta’s, we
respectively obtain $\mathrm{2N}k\mathrm{CA}$ and $\mathrm{2NPD}k\mathrm{CA}$.

An _alternating machine_ must use two groups of inner states: existential
states and universal states. We are concerned with the number of times that
such a machine switches between existential and universal inner states. When
this number is upper-bounded by $k$ ($k\geq 0$) along all computation paths of
$M$ on any input $x$, the machine is said to have at most $k+1$
_alternations_. For any $k\geq 1$, the complexity class
$1\Sigma_{k}\mathrm{PDCA}$ (resp., $2\Sigma_{k}\mathrm{PDCA}$) is composed of
all languages recognized by _one-way_ (resp., _two-way_) _alternating
1-counter pushdown automata_ running in polynomial time with at most $k$
alternations starting with existential inner states. Note that
$1\Sigma_{1}\mathrm{PDCA}$ coincides with $\mathrm{1NPDCA}$.

The notion of _turns_ was studied initially by Ginsburg and Spanier [6]. Turn-
restricted counter automata were called _reversal bounded_ in the past
literature. A 1ncta is said to _make a turn_ along a certain accepting
computation path if the stack height (i.e., the size of stack’s content)
changes from nondecreasing to decreasing exactly once. A _1-turn 1ncta_ is a
1ncta that makes at most one turn during each computation. We add the prefix
“1t” to express the restriction that every underlying machine makes at most
one turn. For example, we write $\mathrm{1t1NCA}$ when all underlying 1ncta’s
in the definition of $\mathrm{1NCA}$ are 1-turn 1ncta’s. Similarly, we define,
e.g., $\mathrm{1t2NPDCA}$ and $\mathrm{1t2}\Sigma_{k}\mathrm{PDCA}$ by
requiring all stacks and counters to make at most one turn. It follows that
$\mathrm{REG}\subseteq\mathrm{1t1NCA}\subseteq\mathrm{1NCA}\subseteq\mathrm{CFL}$,
where $\mathrm{REG}$ (resp., $\mathrm{CFL}$) denotes the class of all regular
(resp., context-free) languages. Notice that $\mathrm{CFL}=\mathrm{1NPD}$. It
also follows that
$\mathrm{L}\subseteq\mathrm{LOG}(\mathrm{1t1NCA})\subseteq\mathrm{LOG(1NCA)}=\mathrm{NL}$.
Conventionally, we write $\mathrm{LOGCFL}$ instead of
$\mathrm{LOG}(\mathrm{CFL})$.

###### Lemma 2.2

For any $k\geq 1$, $\mathrm{2N}k\mathrm{CA}\subseteq\mathrm{NL}$,
$\mathrm{2NPD}k\mathrm{CA}\subseteq\mathrm{LOGCFL}$, and
$2\Sigma_{2}\mathrm{PD}k\mathrm{CA}\subseteq\mathrm{NP}$.

Proof Sketch.  For any index $j\in\mathbb{N}^{+}$, we define
$2\Sigma_{j}\mathrm{AuxPDATI,\\!SP}(t(n),s(n))$ to be the collection of all
decision problems solvable by _two-way alternating auxiliary pushdown
automata_ running within time $t(n)$ using space at most $s(n)$ with at most
$j$ alternations starting with existential inner states. When $j=1$, such
machines are succinctly called _2aux-npda’s_ , which will be used in the proof
of Proposition 2.3. It is known that
$2\Sigma_{1}\mathrm{AuxPDATI,\\!SP}(n^{O(1)},O(\log{n}))$ coincides with
$\mathrm{LOGCFL}$ [15] and
$2\Sigma_{2}\mathrm{AuxPDATI,\\!SP}(n^{O(1)},O(\log{n}))$ coincides with
$\mathrm{NP}$ [8]. Moreover, it is possible to simulate the polynomial time-
bounded behaviors of $k$ counters using an $O(\log{n})$-space bounded
auxiliary work tape. From these facts, the lemma follows immediately. $\Box$

###### Proposition 2.3

$\mathrm{NL}=\mathrm{2N4CA}$ and $\mathrm{LOGCFL}=\mathrm{2NPD3CA}$.

Proof Sketch.  Following an argument of Minsky [11], given a log-space NTM (or
a log-space 2aux-npda), we first simulate the behavior of an
$O(\log{n})$-space auxiliary work tape by two stacks whose alphabets are of
the form $\\{0,1,\bot\\}$. Since the heights of such stacks are upper-bounded
by $O(\log{n})$, the stacks can be further simulated by multiple counters
whose heights are all $n^{O(1)}$-bounded. Let $M$ denote the obtained 2ncta
(or 2npdcta) running in polynomial time.

We remark that Minsky’s method of reducing the number of counters down to two
does not work for machines with few computational resources. Thus, we need to
seek other methods. For this purpose, we review the result of [17], which
makes it possible to simulate two counters by one counter with the heavy use
of an appropriately defined “pairing” function.

###### Claim 1

[17] There exists a fixed deterministic procedure by which any single move of
push/pop operations on two counters of $M$ can be simulated by a series of
$n^{O(1)}$ push/pop operations on one counter with the help of 3 extra
counters. These 3 extra counters are emptied after each simulation and thus
they are reusable for any other purposes. If a stack is further available,
then one extra counter can be simulated by this stack.

The recursive applications of this simulation procedure eventually reduce the
number of counters down to four. If we freely use a stack during the
procedure, then we can further reduce the number of counters down to three.

The first part of the proposition then follows by combining the above claim
with Lemma 2.2. If we use one counter as a stack, then we can further reduce 4
counters to 3 counters. This proves the second part of the proposition. $\Box$

##  3 Combinatorial Number Problems

We study the computational complexity of decision problems whose input
instances are composed of unarized positive integers.

###  3.1 Variations of the Unary 0-1 Knapsack Problem

The starting point of our study on the computational analyses of decision
problems with unarized integer inputs is the _unary 0-1 knapsack problem_ ,
which was introduced in 1985 by Cook [4] as a unary analogue of the _knapsack
problem_.

Unary 0-1 Knapsack Problem (UK):

  * $\circ$

Instance: $(1^{b},1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$, where
$n\in\mathbb{N}^{+}$ and $b,a_{1},a_{2},\ldots,a_{n}$ are all positive
integers.

  * $\circ$

Question: is there a subset $S$ of $[n]$ satisfying $\sum_{i\in S}a_{i}=b$?

It seems more natural to view $\mathrm{UK}$ as a unary analogue of the _subset
sum problem_ , which is closely related to the _2-partition problem_. Let us
consider a unary analogue of this 2-partition problem.

Unary 2 Partition Problem (U2PART):

  * $\circ$

Instance: $(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$, where $n\in\mathbb{N}^{+}$
and $a_{1},a_{2},\ldots,a_{n}$ are all positive integers.

  * $\circ$

Question: is there a subset $S$ of $[n]$ such that $\sum_{i\in
S}a_{i}=\sum_{i\in\overline{S}}a_{i}$, where $\overline{S}=[n]-S$?

The original knapsack problem and the subset sum problem are both proven in
1972 by Karp [10] to be $\mathrm{NP}$-complete. The problems $\mathrm{UK}$ and
$\mathrm{U2PART}$, in contrast, situated within $\mathrm{NL}$.

###### Lemma 3.1

(1) $\mathrm{UK}$ is in $\mathrm{1t1NCA}$. (2) $\mathrm{U2PART}$ is in both
$\mathrm{1NCA}$ and $\mathrm{1t1N2CA}$.

We further introduce two variants of $\mathrm{UK}$ and $\mathrm{U2PART}$,
called $\mathrm{AmbUK}$ and $\mathrm{UASubSum}$ as follows.

Ambiguous UK Problem (AmbUK):

  * $\circ$

Instance:
$((1^{b_{1}},1^{b_{2}},\ldots,1^{b_{m}}),(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}}))$,
where $n,m\in\mathbb{N}^{+}$ and
$b_{1},b_{2},\ldots,b_{m},a_{1},a_{2},\ldots,a_{n}$ are all positive integers.

  * $\circ$

Question: are there an index $j\in[m]$ and a subset $S$ of $[n]$ satisfying
$b_{j}=\sum_{i\in S}a_{i}$?

Unary Approximate Subset Sum Problem (UASubSum):

  * $\circ$

Instance: $((1^{b_{1}},1^{b_{2}}),(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}}))$,
where $n\in\mathbb{N}^{+}$ and $b_{1},b_{2},a_{1},a_{2},\ldots,a_{n}$ are
positive integers.

  * $\circ$

Question: is there a subset $S$ of $[n]$ such that $b_{1}\leq\sum_{i\in
S}a_{i}\leq b_{2}$?

###### Lemma 3.2

(1) $\mathrm{AmbUK}$ is in $\mathrm{1t1NCA}$. (2) $\mathrm{UASubSum}$ is in
$\mathrm{1t1N2CA}$.

Under two different types of log-space reductions, the computational
complexities of $\mathrm{U2PART}$, $\mathrm{AmbUK}$, and $\mathrm{UASubSum}$
are all equal to that of $\mathrm{UK}$.

###### Proposition 3.3

(1) $\mathrm{UK}\equiv^{\mathrm{L}}_{m}\mathrm{U2PART}$. (2)
$\mathrm{UK}\equiv^{\mathrm{L}}_{tt}\mathrm{AmbUK}$. (3)
$\mathrm{UK}\equiv^{\mathrm{L}}_{m}\mathrm{UASubSum}$.

Proof Sketch.  (1) We begin with showing that
$\mathrm{UK}\equiv^{\mathrm{L}}_{m}\mathrm{U2PART}$. Our first goal is to
prove that $\mathrm{UK}\leq^{\mathrm{L}}_{m}\mathrm{U2PART}$ by constructing
an $\mathrm{L}$-m-reduction function $f$. Let
$x=(1^{b},1^{a_{1}},\ldots,1^{a_{n}})$ and let $c=\sum_{i\in[n]}a_{i}$. (a) If
$b=c/2$, then we set $f(x)=x$. (b) If $b<c/2$, then we add a new entry
$a_{n+1}=c-2b$ and set $f(x)=(1^{a_{1}},\ldots,1^{a_{n}},1^{a_{n+1}})$. (c) If
$b>c/2$, then we exchange between $b$ and $c-b$ and apply (b). Our second goal
is to show that $\mathrm{U2PART}\leq^{\mathrm{L}}_{m}\mathrm{UK}$. Letting
$c=\sum_{i}a_{i}$, if $c$ is odd, then we set $f(x)$ to be any fixed rejected
input. Otherwise, we set $b=c/2$ and define
$f(x)=(1^{b},1^{a_{1}},\ldots,1^{a_{n}})$.

(2) It is obvious that $\mathrm{UK}\leq^{\mathrm{L}}_{m}\mathrm{AmbUK}$ by
setting $m=1$ in the definition of $\mathrm{AmbUK}$. Next, we show that
$\mathrm{AmbUK}\leq^{\mathrm{L}}_{tt}\mathrm{UK}$. Let
$w=((1^{b_{1}},1^{b_{2}},\ldots,1^{b_{m}}),(1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}}))$
be any instance of $\mathrm{AmbUK}$. We define an $\mathrm{L}$-tt-reduction
function $f$ as $f(w)=(f_{1}(w),f_{2}(w),\ldots,f_{m}(w))$, where
$f_{i}(w)=(1^{b_{i}},1^{a_{1}},\ldots,1^{a_{n}})$. Clearly, $f$ belongs to
$\mathrm{FL}$. We also define a truth table $E$ as
$E(e_{1},e_{2},\ldots,e_{m})=\bigvee_{i=1}^{m}e_{i}$. It then follows that
$w\in\mathrm{AmbUK}$ iff there exists an index $i\in[m]$ for which
$f_{i}(w)\in\mathrm{UK}$ iff $E(f_{1}(w),f_{2}(w),\ldots,f_{m}(w))=1$.
Therefore, $\mathrm{AmbUK}\leq^{\mathrm{L}}_{tt}\mathrm{UK}$ follows.

(3) To show that $\mathrm{UK}\leq^{\mathrm{L}}_{m}\mathrm{UASubSum}$, it
suffices to set $b_{1}=b_{2}=b$ and define the desired reduction function $f$
to map $(1^{b},1^{a_{1}},\ldots,1^{a_{n}})$ to
$((1^{b_{1}},1^{b_{2}}),(1^{a_{1}},\ldots,1^{a_{n}}))$. On the contrary, we
wish to verify that $\mathrm{UASubSum}\leq^{\mathrm{L}}_{m}\mathrm{UK}$. Let
$w=((1^{b_{1}},1^{b_{2}}),(1^{a_{1}},\ldots,1^{a_{n}}))$ be any input to
$\mathrm{UASubSum}$. If $b_{1}=b_{2}$, then the reduction is trivial. In the
case of $b_{1}>b_{2}$, it suffices to define $f(w)=(1,1^{2})$ since
$w\notin\mathrm{UASubSum}$. In what follows, we assume that $b_{1}<b_{2}$. For
any $S\subseteq[n]$, we define $a_{S}=\sum_{i\in S}a_{i}$. If $a_{[n]}<b_{1}$,
then we construct $f(w)=(1,1^{2})$, which is obviously not in
$\mathrm{UASubSum}$. If $b_{1}\leq a_{[n]}\leq b_{2}$, then we define
$x=(1,1)$. Next, we assume that $b_{2}<a_{[n]}$. Let us define
$a_{n+i}=a_{[n]}+i-1$ for any $i\in[b_{2}-b_{1}+1]$ and let
$b_{max}=b_{2}+a_{[n]}$. We then set
$f(w)=(1^{b_{max}},1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}},1^{a_{n+1}},1^{a_{n+2}},\ldots,1^{a_{n+b_{2}-b_{1}+1}})$.
This concludes that $w\in\mathrm{UASubSum}$ iff $f(w)\in\mathrm{UK}$. $\Box$

Jenner [7] studied a variant of $\mathrm{UK}$, which we intend to call by the
_shift-unary 0-1 knapsack problem_ (shift-UK) in order to signify the use of
the shift-unary representation. She proved that this problem is actually
$\mathrm{NL}$-complete.

Shift-Unary 0-1 Knapsack Problem (shift-UK):

  * $\circ$

Instance: $[1^{q},1^{s}]$ and a series
$([1^{p_{1}},1^{t_{1}}],[1^{p_{2}},1^{t_{2}}],\ldots,[1^{p_{n}},1^{t_{n}}])$
of nonnegative integers represented in shift-unary, where
$q,p_{1},p_{2},\ldots,p_{n}$ are all positive integers and
$s,t_{1},t_{2},\ldots,t_{n}$ are all nonnegative integers.

  * $\circ$

Question: is there a subset $S$ of $[n]$ such that $\sum_{i\in
S}p_{i}2^{t_{i}}=q2^{s}$?

In a similar way, we can define the shift-unary representation versions of
$\mathrm{AmbUK}$, $\mathrm{UASubSum}$, and $\mathrm{U2PART}$, denoted by
$\mathrm{shift}\mbox{-}\mathrm{AmbUK}$,
$\mathrm{shift}\mbox{-}\mathrm{UASubSum}$, and
$\mathrm{shift}\mbox{-}\mathrm{U2PART}$, respectively.

###### Lemma 3.4

The problem $\mathrm{shift}\mbox{-}\mathrm{UK}$ is in $\mathrm{1N6CA}$.

###### Proposition 3.5

$\mathrm{shift}\mbox{-}\mathrm{UK}\equiv^{\mathrm{L}}_{m}\mathrm{shift}\mbox{-}\mathrm{U2PART}\equiv^{\mathrm{L}}_{m}\mathrm{shift}\mbox{-}\mathrm{AmbUK}\equiv^{\mathrm{L}}_{m}\mathrm{shift}\mbox{-}\mathrm{UASubSum}$.

Proof Sketch.  We abbreviate the set
$\\{\mathrm{shift}\mbox{-}\mathrm{U2PART},\mathrm{shift}\mbox{-}\mathrm{AmbUK},\mathrm{shift}\mbox{-}\mathrm{UASubSum}\\}$
as ${\cal S}$. It is easy to obtain, by modifying the proof of Proposition
3.3, that $\mathrm{shift}\mbox{-}\mathrm{UK}\leq^{\mathrm{L}}_{m}{\cal C}$ for
any ${\cal C}\in{\cal S}$. To show that ${\cal
C}\leq^{\mathrm{L}}_{m}\mathrm{shift}\mbox{-}\mathrm{UK}$ for any ${\cal
C}\in{\cal S}$, it suffices to show that ${\cal C}$ belongs to $\mathrm{NL}$
because the $\mathrm{L}$-m-completeness of $\mathrm{shift}\mbox{-}\mathrm{UK}$
[7] guarantees that ${\cal
C}\leq^{\mathrm{L}}_{m}\mathrm{shift}\mbox{-}\mathrm{UK}$. In the case of
${\cal C}=\mathrm{shift}\mbox{-}\mathrm{UASubSum}$, we consider the following
algorithm. On input of the form
$(([1^{q_{1}},1^{s_{1}}],[1^{q_{2}},1^{s_{2}}]),([1^{p_{1}},1^{t_{1}}],\ldots,[1^{p_{n}},1^{t_{n}}]))$,
we nondeterministically choose a number $k\in[t]$ and indices
$i_{1},i_{2},\ldots,i_{k}\in[n]$ and check that $q_{1}2^{s_{1}}\leq\sum_{i\in
S}p_{i}2^{t_{i}}\leq q_{2}2^{s_{2}}$. Note that, by Lemma 2.1, the sum
$\sum_{i\in S}p_{i}2^{t_{i}}$ can be computed using only log space. Hence, $C$
is in $\mathrm{NL}$. The other cases can be similarly handled. $\Box$

From Proposition 3.5, since $\mathrm{shift}\mbox{-}\mathrm{UK}$ is
$\mathrm{NL}$-complete under $\mathrm{L}$-m-reductions [7], we immediately
obtain the following corollary.

###### Corollary 3.6

The problems $\mathrm{shift}\mbox{-}\mathrm{U2PART}$,
$\mathrm{shift}\mbox{-}\mathrm{AmbUK}$, and
$\mathrm{shift}\mbox{-}\mathrm{UASubSum}$ are all $\mathrm{NL}$-complete.

For later references, we introduce another variant of $\mathrm{UK}$. This
variant requires a prohibition of certain successive choices of unarized
integer inputs.

UK with Exception (UKEXC):

  * $\circ$

Instance: $(1^{b},1^{a_{1}},1^{a_{2}},\ldots,1^{a_{n}})$ and
$EXC\subseteq\\{(i,j)\mid i,j\in[n],i<j\\}$ given as a set of pairs
$(1^{i},1^{j})$, where $n\in\mathbb{N}^{+}$ and $b,a_{1},a_{2},\ldots,a_{n}$
are in $\mathbb{N}^{+}$.

  * $\circ$

Question: is there a subset $S=\\{i_{1},i_{2},\ldots,i_{k}\\}$ of $[n]$ with
$k\in\mathbb{N}^{+}$ and $i_{1}<i_{2}<\cdots<i_{k}$ such that (i) $\sum_{i\in
S}a_{i}=b$ and (ii) no $j\in[k-1]$ satisfies $(i_{j},i_{j+1})\in EXC$?

Note that, when $EXC=\varnothing$, $\mathrm{UKEXC}$ is equivalent to
$\mathrm{UK}$.

###### Lemma 3.7

$\mathrm{UKEXC}$ is in $\mathrm{2N3CA}$.

Proof Sketch.  We nondeterministically choose $1^{a_{i}}$ by reading an input
from left to right. We use two counters to remember the index $i$ (in the form
of $1^{i}$) for checking that the next possible choice, say, $1^{a_{j}}$
satisfies $(i,j)\notin EXC$. The third counter is used to store $1^{b}$ and
then sequentially pop $1^{a_{i}}$ for the chosen indices $i$. $\Box$

We also introduce another variant of $\mathrm{UK}$, which concerns
simultaneous handling of input integers.

Simultaneous Unary 0-1 Knapsack Problem (SUK):

  * $\circ$

Instance: $(1^{b_{1}},1^{a_{11}},1^{a_{12}},\ldots,1^{a_{1n}}),\ldots,$
$(1^{b_{m}},1^{a_{m1}},1^{a_{m2}},\ldots,1^{a_{mn}})$, where
$m,n\in\mathbb{N}^{+}$ and $b_{i}$ and $a_{ij}$ ($i\in[n],j\in[m]$) are all
positive integers.

  * $\circ$

Question: is there a subset $S\subseteq[n]$ such that $\sum_{j\in
S}a_{ij}=b_{i}$ for all indices $i\in[m]$?

The complexity class $\mathrm{1t}1\Sigma_{2}\mathrm{PDCA}$ is the one-way
restriction of $\mathrm{1t2}\Sigma_{2}\mathrm{PDCA}$.

###### Lemma 3.8

The problem $\mathrm{SUK}$ is in $\mathrm{1t}1\Sigma_{2}\mathrm{PDCA}$.

Proof Sketch.  To recognize $\mathrm{SUK}$, let us consider a _one-way
alternating counter pushdown automaton_ (or a 1apdcta) that behaves as
follows. Given an input $x$ of the form
$(1^{b_{1}},1^{a_{11}},1^{a_{12}},\ldots,1^{a_{1n}}),\ldots,$
$(1^{b_{m}},1^{a_{m1}},1^{a_{m2}},\ldots,1^{a_{mn}})$, we call each segment
$(1^{b_{i}},1^{a_{i1}},1^{a_{i2}},\ldots,1^{a_{in}})$ of $x$ by the _$i$ th
block_ of $x$.

In existential inner states, we first choose a string $w\in\\{0,1\\}^{*}$ and
push it into a stack, where $w=e_{1}e_{2}\cdots e_{n}$ indicates that, for any
$j\in[n]$, we select the $j$th entry from every block exactly when $e_{j}=1$.
Let $A_{w}=\\{j\in[n]\mid e_{j}=1\\}$. In universal inner states, we then
check whether $b_{i}=\sum_{j\in A_{w}}a_{ij}$ holds for all $i\in[m]$. This
last procedure is achieved by first storing $1^{b_{i}}$ into a counter. As
popping the values $e_{j}$ one by one from the stack, if $j\in A_{w}$, then we
decrease the counter by $a_{ij}$. Otherwise, we do nothing. When either the
stack gets empty or the assigned block $(1^{a_{i1}},\ldots,1^{a_{in}})$ of $x$
is finished, if the stack is empty and the counter becomes $0$, then we accept
$x$; otherwise, we reject $x$. Note that the stack and the counter make only
1-turns and the input-tape head moves only in one direction. $\Box$

###  3.2 Unary Bounded Correspondence Problem

We turn our attention to the _bounded Post correspondence problem_ (BPCP),
which is a well-known problem of determining whether, given a set
$\\{(a_{i},b_{i})\\}_{i\in[n]}$ of binary string pairs and a number $k\geq 1$,
a certain sequence $(i_{1},i_{2},\ldots,i_{t})$ of elements in $[n]$ with
$t\leq k$ satisfies $a_{i_{1}}a_{i_{2}}\cdots
a_{i_{t}}=b_{i_{1}}b_{i_{2}}\cdots b_{i_{t}}$. This problem is known to be
$\mathrm{NP}$-complete [2]. When we replace binary strings $a_{i}$ and $b_{i}$
by unary strings, we obtain the following “unary” variant of $\mathrm{PCP}$.

Unary Bounded Correspondence Problem (UBCP):

  * $\circ$

Instance: $((a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n},b_{n}))$ for unary
strings $a_{1},a_{2},\ldots,a_{n},b_{1},b_{2},\ldots,b_{n}\in 1^{+}$ and
$1^{k}$ for $k\in\mathbb{N}^{+}$.

  * $\circ$

Question: is there a sequence $(i_{1},i_{2},\ldots,i_{t})$ of elements in
$[n]$ with $t\in[k]$ satisfying $a_{i_{1}}a_{i_{2}}\cdots
a_{i_{t}}=b_{i_{1}}b_{i_{2}}\cdots b_{i_{t}}$?

Since $a_{i}$ and $b_{i}$ are unary strings, the above requirement
$a_{i_{1}}\cdots a_{i_{t}}=b_{i_{1}}\cdots b_{i_{t}}$ is equivalent to
$\sum_{j\in S}|a_{j}|=\sum_{j\in S}|b_{j}|$, where $|a_{j}|$ and $|b_{j}|$
mean the lengths of strings $a_{j}$ and $b_{j}$, respectively.

###### Lemma 3.9

$\mathrm{UBCP}$ belongs to $\mathrm{1t1N2CA}$.

###### Proposition 3.10

$\mathrm{UK}\leq^{\mathrm{L}}_{m}\mathrm{UBCP}\leq^{\mathrm{L}}_{m}\mathrm{AmbUK}$.

Proof Sketch.  Here, we only show the last reduction
$\mathrm{UBCP}\leq^{\mathrm{L}}_{m}\mathrm{AmbUK}$. Let
$w=((a_{1},b_{1}),\ldots,(a_{n},b_{n}))$ be any instance to $\mathrm{UBCP}$.
Assume that, for any $i\in[n]$, $a_{i}=1^{k_{i}}$ and $b_{i}=1^{l_{i}}$ for
certain numbers $k_{i},l_{i}\in\mathbb{N}^{+}$. Let
$m=\max\\{\sum_{i\in[n]}k_{i},\sum_{i\in[n]}l_{i}\\}$. Note that
$|S|\leq\sum_{i\in S}k_{i}\leq m$ and $|S|\leq\sum_{i\in S}l_{i}\leq m$ for
any $S\subseteq[n]$. We then set $c_{i}=m-(k_{i}-l_{i})$ for each $i\in[n]$.
We remark that $\sum_{i\in S}c_{i}=m|S|-(\sum_{i\in S}k_{i}-\sum_{i\in
S}l_{i})\geq m|S|-(m-|S|)=m(|S|-1)+|S|\geq 0$ for any nonempty subset $S$ of
$[n]$. If $w\in\mathrm{UBCP}$, then there is a nonempty set $S\subseteq[n]$
such that $\sum_{i\in S}k_{i}=\sum_{i\in S}l_{i}$, that is, $\sum_{i\in
S}(k_{i}-l_{i})=0$. It then follows that $\sum_{i\in S}c_{i}=m|S|$.

We also check if $\sum_{i\in[n]}k_{i}=\sum_{i\in[n]}l_{i}$ or if
$k_{i_{0}}=l_{i_{0}}$ for a certain index $i_{0}\in[n]$. If this is true, then
we know that $S=[n]$ or $\\{i_{0}\\}$. Otherwise, we set $d_{i}=i\cdot m$ for
each $i\in[2,n-1]_{\mathbb{Z}}$ and then define
$u=((1^{d_{2}},1^{d_{3}},\ldots,1^{d_{n-1}}),(1^{c_{1}},1^{c_{2}},\ldots,1^{c_{n}}))$.
It follows that $w\in\mathrm{UBCP}$ iff $u\in\mathrm{AmbUK}$. $\Box$

###### Corollary 3.11

$\mathrm{UK}\equiv^{\mathrm{L}}_{tt}\mathrm{UBCP}$.

##  4 Graph Problems

We look into decision problems that are related to graphs, in particular,
weighted graphs in which either vertices or edges are labeled with “weights”.
Here, we study the computational complexity of these specific problems.

We begin with edge-weighted path problems, in which we search for a simple
path whose weight matches a target unarized number, which is given in unary.
We consider, in particular, _directed acyclic graphs_ (or dags) whose edges
are further labeled with weights, which are given in unary.

For the purpose of this work, a dag $G=(V,E)$ given as part of inputs to an
underlying machine is assumed to satisfy that $V$ is a subset of
$\mathbb{N}^{+}$, e.g., $V=\\{i_{1},i_{2},\ldots,i_{n}\\}$ for
$i_{1},i_{2},\ldots,i_{n}\in\mathbb{N}^{+}$. We also use the following
specific encoding of $G$. Given a vertex $i$, we write $E[i]$ for the set of
all adjacent vertices entering from $i$, namely, $\\{j\in V\mid(i,j)\in E\\}$.
When $E[i]$ equals $\\{j_{1},j_{2},\ldots,j_{n}\\}$ with
$j_{1}<j_{2}<\cdots<j_{n}$, we express it in the “multi-unary” form of
$(1^{i},1^{j_{1}},1^{j_{2}},\ldots,1^{j_{n}})$. The _unary adjacency list
representation_ $UAL_{G}$ of $G$ is of the form
$((1^{i_{1}},1^{j_{i_{1},1}},1^{j_{i_{1},2}},\ldots,1^{j_{i_{1},k_{1}}}),\ldots,(1^{i_{n}},1^{j_{i_{n},1}},1^{j_{i_{n},2}},\ldots,1^{j_{i_{n},k_{n}}}))$
with $k_{i}\in\mathbb{N}$ if $V=\\{i_{1},i_{2},\ldots,i_{n}\\}$ with
$i_{1}<i_{2}<\cdots<i_{n}$ and
$E[i_{s}]=\\{j_{i_{s},1},j_{i_{s},2},\ldots,j_{i_{s},k_{s}}\\}$ with
$j_{i_{s},1}<j_{i_{s},2}<\cdots<j_{i_{s},k_{s}}$ for any $s\in[n]$.

Edge-Weighted Path Problem (EWPP)

  * $\circ$

Instance: a dag $G=(V,E)$ with $V\subseteq\mathbb{N}^{+}$ given in the form of
$UAL_{G}$, a vertex $s\in V$ given as $1^{s}$, edge weights
$w(i,j)\in\mathbb{N}^{+}$ given as $1^{w(i,j)}$ for all edges $(i,j)\in E$,
and $1^{c}$ with $c\in\mathbb{N}^{+}$, provided that edges are enumerated
according to the linear order $<_{[n]}$.

  * $\circ$

Question: is there a vertex $v\in V$ such that the total edge weight of a path
from $s$ to $v$ equals $c$?

In comparison, the _graph connectivity problem_ for directed “unweighted”
graphs (DSTCON) is known to be $\mathrm{NL}$-complete [9].

###### Lemma 4.1

$\mathrm{EWPP}$ is in $\mathrm{NL}$.

When each edge weight is $1$, the total weight of a path is the same as the
length of the path. This fact makes us introduce another decision problem. A
_sink_ of a directed graph is a vertex of outdegree $0$ in the graph.

Exact Path Length Problem (EPLP)

  * $\circ$

Instance: a dag $G=(V,E)$ with $V\subseteq\mathbb{N}^{+}$ given as $UAL_{G}$,
a vertex $s\in V$ given as $1^{s}$, and $1^{c}$ with $c\in\mathbb{N}^{+}$.

  * $\circ$

Question: is there a sink $v$ of $G$ such that a path from $s$ to $v$ has
length exactly $c$?

###### Proposition 4.2

$\mathrm{EWPP}\equiv^{\mathrm{L}}_{m}\mathrm{EPLP}$.

Proof Sketch.  Firstly, we show that
$\mathrm{EPLP}\leq^{\mathrm{L}}_{m}\mathrm{EWPP}$. Given an instance
$x=(G,s,1^{c})$ of $\mathrm{EPLP}$ with $G=(V,E)$, we define another instance,
say, $y$ of $\mathrm{EWPP}$ as follows. For every leaf $v$ of $G$, we add a
new vertex $\bar{v}$ and a new edge $(v,\bar{v})$ to $G$ and obtain the new
vertex set $V^{\prime}$ and the new edge set $E^{\prime}$. Consider the
resulting graph $G^{\prime}=(V^{\prime},E^{\prime})$. Let $n=|V^{\prime}|$. We
define $w(u,v)=1$ for all pairs $(u,v)\in E$ and additionally we set
$w(v,\bar{v})=n+1$ for any old leaf $v\in V$. Let $c^{\prime}=c+n+1$. We
define $y=(G^{\prime},\\{w(e)\\}_{e\in E^{\prime}},1^{c^{\prime}})$. We want
to verify that (*) $x\in\mathrm{EPLP}$ iff $y\in\mathrm{EWPP}$.

To prove (*), let us assume that $x\in\mathrm{EPLP}$. We then take a
length-$c$ path $\gamma=(v_{0},v_{1},\ldots,v_{c})$ of $G$ with $v_{0}=s$ and
$v_{c}$ is a leaf. Consider $y$ and
$\gamma^{(+)}=(v_{0},v_{1},\ldots,v_{c},\bar{v}_{c})$. The total weight of
$\gamma^{(+)}$ in $G^{\prime}$ is $c+w(v_{c},\bar{v}_{c})=c+n+1=c^{\prime}$.
Hence, $y$ is in $\mathrm{EWPP}$. Conversely, assume that $y\in\mathrm{EWPP}$
and consider a path $\gamma=(v_{0},v_{1},\ldots,v_{k})$ of $G^{\prime}$ with
$v_{0}=s$ satisfying $\sum_{i=0}^{k}w(v_{i},v_{i+1})=c^{\prime}$. Since
$n=|V^{\prime}|$, $\gamma$ must include a leaf. Hence, $v_{k}$ must be
$\bar{v}_{k-1}$. Moreover, $k-1=c$ follows. The path
$\gamma^{(-)}=(v_{0},v_{1},\ldots,v_{k-1})$ is a path from $s$ to a leaf of
$G$ and its length is exactly $c$. This implies that $x\in\mathrm{EPLP}$.

Secondly, we show that $\mathrm{EWPP}\leq^{\mathrm{L}}_{m}\mathrm{EPLP}$. Let
$x=(G,s,\\{w(e)\\}_{e\in E},1^{c})$ be any instance of $\mathrm{EWPP}$. We
construct an instance of $\mathrm{EPLP}$ as follows. For each $(u,v)\in E$
with $w(u,v)=1^{k}$, we introduce $k+1$ extra vertices
$\\{\bar{v},u^{\prime}_{1},u^{\prime}_{2},\ldots,u^{\prime}_{k}\\}$ and extra
edges
$\\{(u,u^{\prime}_{1}),(u^{\prime}_{1},u^{\prime}_{2}),\ldots,(u^{\prime}_{i},u^{\prime}_{i+1}),(u^{\prime}_{k},v),(u^{\prime}_{k},\bar{v})\mid
i\in[k-2]\\}$. Those edges form two paths from $u$ to $v$ and $u$ to $\bar{v}$
of length exactly $k$. Notice that $\bar{v}$ becomes a new leaf. Let
$V^{\prime}$ and $E^{\prime}$ denote the extended sets of $V$ and $E$,
respectively, and set $G^{\prime}=(V^{\prime},E^{\prime})$. For the instance
$y=(G^{\prime},s,1^{c})$, it is possible to prove that $x\in\mathrm{EWPP}$ iff
$y\in\mathrm{EPLP}$. $\Box$

We then obtain the following $\mathrm{NL}$-completeness result.

###### Proposition 4.3

$\mathrm{EWPP}$ and $\mathrm{EPLP}$ are both $\mathrm{L}$-m-complete for
$\mathrm{NL}$.

Proof Sketch.  Here, we wish to prove (*)
$L\leq^{\mathrm{L}}_{m}\mathrm{EPLP}$ for any language $L$ in $\mathrm{1NCA}$.
If this is true, then all languages in $\mathrm{NL}$ are
$\mathrm{L}$-m-reducible to $\mathrm{EPLP}$ since
$\mathrm{LOG(1NCA)}=\mathrm{NL}$. Moreover, since $\mathrm{EWPP}$ belongs to
$\mathrm{NL}$ by Lemma 4.1, $\mathrm{EPLP}$ is also in $\mathrm{NL}$.
Therefore, $\mathrm{EPLP}$ is $\mathrm{L}$-m-complete for $\mathrm{NL}$. Since
$\mathrm{EWPP}\equiv^{\mathrm{L}}_{m}\mathrm{EPLP}$ by Proposition 4.2, we
also obtain the $\mathrm{NL}$-completeness of $\mathrm{EWPP}$.

To show the statement (*), let us take any 1ncta $M$ and consider surface
configurations of $M$ on input $x$. Note that, since surface configurations
have size $O(\log{|x|})$, we can express them as unary-form positive integers.
Between two surface configurations, we define a single-step transition
relation $\vdash_{M}$. We then define a computation graph
$G_{x}=(V_{x},E_{x})$ of $M$ on the input $x$. The vertex set $V_{x}$ is
composed of all possible surface configurations of $M$ on $x$. We further
define $E_{x}$ to be the set of all pairs $(v_{1},v_{2})$ of surface
configurations satisfying $v_{1}\vdash_{M}v_{2}$. The root $s$ of $G_{x}$ is
set to be the initial surface configuration of $M$. It then follows that $x\in
L(M)$ iff $(UAL_{G_{x}},1^{s},1^{|x|+2})\in\mathrm{EPLP}$. $\Box$

Let us argue how $\mathrm{EWPP}$ is related to $\mathrm{UKEXC}$ and
$\mathrm{UK}$. To see the desired relationships, we introduce two restricted
variants of $\mathrm{EWPP}$. We say that a dag $G=(V,E)$ with
$V\subseteq\mathbb{N}^{+}$ is _topologically ordered_ if, for any two vertices
$i,j\in V$, $(i,j)\in E$ implies $i<j$. We define $\mathrm{TO\mbox{-}EWPP}$ as
the restriction of $\mathrm{EWPP}$ onto instances that are topologically
ordered. A dag $G=(V,E)$ is _edge-closed_ if, for any three vertices $u,v,w\in
V$, (1) $(u,v)\in E$ and $(v,w)\in E$ imply $(u,w)\in E$ and (2) $(u,w)\in E$
and $(v,w)\in E$ imply either $(u,v)\in E$ or $(v,u)\in E$. We write
$\mathrm{EC\mbox{-}EWPP}$ for $\mathrm{TO\mbox{-}EWPP}$ whose instance graphs
are all edge-closed.

###### Proposition 4.4

(1) $\mathrm{TO\mbox{-}EWPP}\equiv^{\mathrm{L}}_{m}\mathrm{UKEXC}$. (2)
$\mathrm{EC\mbox{-}EWPP}\equiv^{\mathrm{L}}_{m}\mathrm{UK}$.

Proof Sketch.  In what follows, we focus only on (1). We first show that
$\mathrm{UKEXC}\leq^{\mathrm{L}}_{m}\mathrm{TO\mbox{-}EWPP}$. Given an
instance $x=((1^{b},1^{a_{1}},\ldots,1^{a_{n}}),EXC)$ of $\mathrm{UKEXC}$, we
construct an associated instance, say, $y$ of $\mathrm{TO\mbox{-}EWPP}$ as
follows. We then define $V=\\{s,v_{1},v_{2},\ldots,v_{n}\\}$ and
$E=\\{(v_{i},v_{j})\mid i,j\in[n],i<j,(i,j)\notin EXC\\}\cup\\{(s,v_{j})\mid
j\in[n]\\}$. It follows that $G=(V,E)$ is directed, acyclic, and topologically
ordered. Furthermore, we define edge weights as $w(v_{i},v_{j})=a_{i}$ and
$w(s,v_{j})=1$ for any $(v_{i},v_{j}),(s,v_{j})\in E$. Finally, we set
$c=b+1$. Let us consider $y=(G,\\{1^{w(e)}\\}_{e\in E},1^{c})$. It is possible
for us to verify that $x\in\mathrm{UKEXC}$ iff $y\in\mathrm{TO\mbox{-}EWPP}$.
This implies $\mathrm{UKEXC}\leq^{\mathrm{L}}_{m}\mathrm{TO\mbox{-}EWPP}$.

Conversely, we intend to verify that
$\mathrm{TO\mbox{-}EWPP}\leq^{\mathrm{L}}_{m}\mathrm{UKEXC}$. Assume that
$x=(G,s,\\{1^{w(e)}\\}_{e\in E},1^{c})$ with $G=(V,E)$ is any instance of
$\mathrm{TO\mbox{-}EWPP}$. An associated instance $y$ of $\mathrm{UKEXC}$ is
constructed as follows. Firstly, we assume that $G$ is acyclic because,
otherwise, we convert $G$ to an acyclic graph
$G^{\prime}=(V^{\prime},E^{\prime})$ by setting $V^{\prime}=\\{((i,v)\mid
i\in[|V|],v\in V\\}$ and $E^{\prime}=\\{((i,u),(i+1,v))\mid
i\in[|V|-1],(u,v)\in E\\}$. For simplicity, we further assume that
$V=[2,n]_{\mathbb{Z}}$ and $s$ is vertex $2$. We define an encoding $\langle
i,j\rangle$ of two distinct vertices $i,j\in[n]$ as $\langle
i,j\rangle=(i-1)n+j$. We consider only a unique connected component including
$s$ because any other connected component is irrelevant. Hereafter, we assume
that this connected component contains all vertices in $V$. We expand $G$ to
$G^{\prime}=(V^{\prime},E^{\prime})$ by setting $V^{\prime}=V\cup\\{1\\}$ and
$E^{\prime}=E\cup\\{(1,j)\mid j\in[2,n]_{\mathbb{Z}}\\}$. As for new weights,
we set $w^{\prime}(i,j)=w(i,j)$ for any $(i,j)\in E$ and
$w^{\prime}(1,j)=w_{*}+1$ for any $j\in[2,n]_{\mathbb{Z}}$, where
$w_{*}=\sum_{(i,j)\in E}w(i,j)$.

We further set $a_{\langle i,j\rangle}=w(i,j)$ if $(i,j)\in E$. Moreover, let
$a_{\langle 1,j\rangle}=w_{*}+1$ for any $j\in[2,n]_{\mathbb{Z}}$. For any
other pair $(i,j)$, the value $a_{\langle i,j\rangle}$ is not defined. Let $A$
denote the set of all $a_{\langle i,j\rangle}$’s that are defined. Assume that
$A$ has the form $\\{a_{k_{1}},a_{k_{2}},\ldots,a_{k_{m}}\\}$ with $m\leq
n^{2}$, where $k_{1}<k_{2}<\cdots<k_{m}$. We write $K$ for the set
$\\{k_{1},k_{2},\ldots,k_{m}\\}$. The set $EXC$ is defined to be the union of
the following sets: $\\{(\langle i,j\rangle,\langle
i^{\prime},j^{\prime}\rangle)\mid i,j,i^{\prime},j^{\prime}\in[n],(\langle
i,j\rangle\not<\langle i^{\prime},j^{\prime}\rangle\vee j\neq i^{\prime}\vee
i=j^{\prime}),(i,v)\in E,({i^{\prime}},{j^{\prime}})\in E\\}$, $\\{(\langle
i,j\rangle,\langle i^{\prime},j^{\prime}\rangle)\mid
i,i^{\prime},j,j^{\prime}\in[n],\langle i,j\rangle<\langle
i^{\prime},j^{\prime}\rangle,((i,j)\notin
E\vee({i^{\prime}},{j^{\prime}})\notin E)\\}$, and $\\{(\langle
i,j\rangle,\langle 1,j^{\prime}\rangle)\mid
i,j,j^{\prime}\in[2,n]_{\mathbb{Z}}\\}$. Let $b=c+w_{*}+1$.

We define the desired instance $y$ as
$y=((1^{b},1^{a_{k_{1}}},1^{a_{k_{2}}},\ldots,1^{a_{k_{m}}}),EXC)$. For this
instance $y$, we can prove that $x\in\mathrm{TO\mbox{-}EWPP}$ iff
$y\in\mathrm{UKEXC}$. $\Box$

##  5 Lattice Problems

Let us discuss lattice problems. A _lattice_ is a set of integer linear
combinations of basis vectors. Here, we deal only with the case where bases
are taken from $\mathbb{Z}^{n}$ for a certain $n\in\mathbb{N}^{+}$. The
decision version of the _closest vector problem_ (CVP) is known to be
$\mathrm{NP}$-complete [16]. We then consider a variant of $\mathrm{CVP}$. To
fit into our setting of unary-form integers, a simple norm notion of the _max
norm_ $\|\cdot\|_{\infty}$ from Section 2.1. In a syntactic similarity, we
further introduce the notation $\|v\|_{\min}$ to express
$\min\\{|v_{i}|:i\in[n]\\}$ for any real-valued vector
$v=(v_{1},v_{2},\ldots,v_{n})$. Notice that $\|v\|_{\min}$ does not serve as a
true “distance”. For convenience, ${\cal L}(v_{1},v_{2},\ldots,v_{m})$ denotes
the lattice spanned by a given set $\\{v_{1},v_{2},\ldots,v_{m}\\}$ of basis
vectors.

Unary Max-Norm Closest Vector Problem (UCVPmax):

  * $\circ$

Instance: $1^{b}$ for a positive integer $b$, a tuple $(1^{\langle
v_{i}[1]\rangle},1^{\langle v_{i}[2]\rangle},\ldots,1^{\langle
v_{i}[n]\rangle})$ for a set $\\{v_{1},v_{2},\ldots,v_{m}\\}$ of lattice bases
with $v_{i}=(v_{i}[1],v_{i}[2],\ldots,v_{i}[n])\in\mathbb{Z}^{n}$, and a tuple
$(1^{\langle x_{0}[1]\rangle},1^{\langle x_{0}[2]\rangle},\ldots,1^{\langle
x_{0}[n]\rangle})$ for a target vector
$x_{0}=(x_{0}[1],x_{0}[2],\ldots,x_{0}[n])\in\mathbb{Z}^{n}$.

  * $\circ$

Question: is there a lattice vector $w$ in ${\cal
L}(v_{1},v_{2},\ldots,v_{m})$ such that the max norm $\|w-x_{0}\|_{\infty}$ is
at most $b$?

In the above definition of $\mathrm{UCVP}_{\max}$, we replace
$\|\cdot\|_{\infty}$ by $\|\cdot\|_{min}$ and then obtain
$\mathrm{UCVP}_{\min}$.

For simplicity, in what follows, we intend to write $\bar{v}$ for $(1^{\langle
v[1]\rangle},1^{\langle v[2]\rangle},\ldots,1^{\langle v[n]\rangle})$ if
$v=(v[1],v[2],\ldots,v[n])$.

###### Proposition 5.1

$\mathrm{SUK}\leq^{\mathrm{L}}_{m}\mathrm{UCVP}_{\max}$.

Proof Sketch.  In a similar way to obtaining $\mathrm{SUK}$ from
$\mathrm{UK}$, we can introduce a variant of $\mathrm{U2PART}$, called the
_simultaneous unary 2 partition problem_ (SU2PART). It is possible to prove
that $\mathrm{SUK}\leq^{\mathrm{L}}_{m}\mathrm{SU2PART}$. It therefore
suffices to verify that
$\mathrm{SU2PART}\leq^{\mathrm{L}}_{m}\mathrm{UCVP}_{\max}$.

Let $x=(a_{1},a_{2},\ldots,a_{m})$ with
$a_{j}=(1^{a_{j1}},1^{a_{j2}},\ldots,1^{a_{jn}})$ for any $j\in[m]$ be any
instance of $\mathrm{SU2PART}$. Let $d_{j}=\sum_{i\in[n]}a_{ji}$ for each
$j\in[m]$ and set $d_{max}=\max_{j\in[m]}\\{d_{j}\\}$. Given any $j\in[m]$ and
$i\in[n]$, we further set $a^{\prime}_{ji}=d_{max}a_{ji}$ and
$d^{\prime}_{j}=d_{max}d_{j}$. Let us define $n$ vectors
$v_{1},v_{2},\ldots,v_{n}$ as
$v_{1}=(a^{\prime}_{11},a^{\prime}_{21},\ldots,a^{\prime}_{m1},2,0,0,\ldots,0)$,
$v_{2}=(a^{\prime}_{21},a^{\prime}_{22},\ldots,a^{\prime}_{2n},0,2,0,\ldots,0)$,
$\ldots$,
$v_{n}=(a^{\prime}_{n1},a^{\prime}_{n2},\ldots,a^{\prime}_{nm},0,0,0,\ldots,0,2)$.
Moreover, we set $x_{0}=(\lfloor d^{\prime}_{1}/2\rfloor,\lfloor
d^{\prime}_{2}/2\rfloor,\ldots,\lfloor d^{\prime}_{m}/2\rfloor,1,1,\ldots,1)$
and $b=1$. We then define $y$ to be
$(1^{b},\bar{v}_{1},\bar{v}_{2},\ldots,\bar{v}_{n},\bar{x}_{0})$. Clearly, $y$
is an instance of $\mathrm{UCSP}_{\max}$. It then follows that
$x\in\mathrm{U2PART}$ iff $y\in\mathrm{UCVC}_{\max}$. $\Box$

###### Lemma 5.2

(1) $\mathrm{UCVP}_{\max}\in\mathrm{1t2}\Sigma_{2}\mathrm{PDCA}$. (2)
$\mathrm{UCVP}_{\min}\in\mathrm{1t2NCA}$.

It is not clear that $\mathrm{UCVP}_{\max}$ belongs to $\mathrm{1t2NPDCA}$ or
even $\mathrm{P}$.

Next, we look into another relevant problem, known as the _shortest vector
problem_. We consider its variant.

Unary Max-Norm Shortest Vector Problem (USVPmax):

  * $\circ$

Instance: $1^{b}$ with $b\in\mathbb{N}^{+}$ and a tuple $(1^{\langle
v_{i}[1]\rangle},1^{\langle v_{i}[2]\rangle},\ldots,1^{\langle
v_{i}[n]\rangle})$ for a set $\\{v_{1},v_{2},\ldots,v_{m}\\}$ of lattice bases
with $v_{i}=(v_{i}[1],v_{i}[2],\ldots,v_{i}[n])\in\mathbb{Z}^{n}$.

  * $\circ$

Question: is there a “non-zero” lattice vector $w$ in ${\cal
L}(v_{1},v_{2},\ldots,v_{m})$ such that the max norm $\|w\|_{\infty}$ is at
most $b$?

Similarly, we can define $\mathrm{USVP}_{\min}$ by replacing
$\|\cdot\|_{\infty}$ with $\|\cdot\|_{\min}$. In a way similar to prove Lemma
5.2, we can prove that
$\mathrm{USVP}_{\max}\in\mathrm{1t2}\Sigma_{2}\mathrm{PDCA}$. Moreover, the
following relations hold.

###### Lemma 5.3

$\mathrm{USVP}_{\min}\leq^{\mathrm{L}}_{tt}\mathrm{UCVP}_{\min}$ and
$\mathrm{USVP}_{\max}\leq^{\mathrm{L}}_{tt}\mathrm{UCVP}_{\max}$.

We do not know if
$\mathrm{USVP}_{\min}\equiv^{\mathrm{L}}_{tt}\mathrm{UCVP}_{\min}$ and
$\mathrm{USVP}_{\max}\equiv^{\mathrm{L}}_{tt}\mathrm{UCVP}_{\max}$.

## References

  * [1] Cho, S., Huynh, D.T.: On a complexity hierarchy between L and NL. Inform. Process. Lett. 29, 177–182 (1988)
  * [2] Constable, R.L., Hunt III, H.B., Sahni, S.: On the computational complexity of scheme equivalence. Report No. 74-201, Dept. of Computer Science, Cornell University (1974)
  * [3] Cook, S.A.: Deterministic CFLs are accepted simultaneously in polynomial time and log squared space. In the Proceedings of the 1lth Annual ACM Symposium on Theory of Computing, pp. 338–345 (1979)
  * [4] Cook, S.A.: A taxonomy of problems with fast parallel algorithms. Inform. Control 64 (1985) 2–22.
  * [5] Garey, M.R., Johnson, D.S.: Computers and Interactability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York (1979)
  * [6] Ginsburg, G., E. H. Spanier, E.H.: Finite-turn pushdown automata. SIAM J. Control 4, 429–453 (1966)
  * [7] Jenner, B.: Knapsack problems for NL. Inform. Process. Lett. 54, 169–174 (1995)
  * [8] Jenner, B., Kirsg, B.: Characterizing the polynomial hierarchy by alternating pushdown automata. RAIRO–Theoret. Inform. App. 23, 87–99 (1989)
  * [9] Jones, N.D., Lien, Y.E., Laaser, W.T.: New problems complete for nondeterministic log space. Math. Systems Theory 10, 1–17 (1976)
  * [10] Karp, R.M.: Reducibility among combinatorial problems. In: R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations. Plenum Press, New York, pp. 85–103 (1972)
  * [11] Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ (1967)
  * [12] Monien, B., Sudborough, I.H.: Foraml language theory. In: Formal Language Theory, R. V. Book (ed), Academic Press, New York (1980).
  * [13] Reingold, O.: Undirected connectivity in log-space. J. ACM 55, article 17 (2008)
  * [14] Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In the Proc. of the 5th Ann. ACM Symp. on Theory of Computing, pp. 1–9 (1973)
  * [15] Sudborough, I.H.: On the tape complexity of determinsitic context-free languages. J. ACM 25, 405–414 (1978)
  * [16] van Emde Boas, P.: Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Report No. 81-04, Department of Mathematice, University of Amsterdam (1981)
  * [17] T. Yamakami. Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and multiple counters. Manuscript, 2023.


# Delayed Blockchain Protocols

Drew Stone  University of Pennsylvania, Mathematics Department
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Given the parallels between game theory and consensus, it makes sense to
intelligently design blockchain or DAG protocols with an incentive-compatible-
first mentality. To that end, we propose a new blockchain or DAG protocol
enhancement based on delayed rewards. We devise a new method for imposing
slashing conditions on miner behavior, using their delayed rewards as stake in
a Proof of Work system. Using fraud proofs, we can slash malicious miner
behavior and reward long-lived, honest behavior.

###### Key words and phrases:

Distributed systems, consensus, game theory, blockchains

##  1\. Introduction

The hype around blockchains and DAGs (which we refer to interchangeably) has
outlived their ability to compete against centralized service providers. The
payment processors and money services businesses still scale more efficiently
and more cheaply versus their blockchain competitors. This, however, has not
stopped the rise in research around scalability and security-first designs. By
building with new scalable and secure consensus protocols, these networks
stand to realize the potential of decentralized cryptocurrencies. New designs,
however, introduce new attack vectors. They change up the incentive structure
of the underlying game by potentially reducing costs of attacks. With new
scalable designs comes the hope for new game theoretic techniques for dealing
with uncertain consequences.

The parallels between game theory and consensus, as exhibited by the repeated
nature of mining for rewards, represent clear indicators in the usefulness of
game theoretic techniques towards protocol design. Using inspiration from
Proof of Stake protocols, especially slashing conditions, we develop a
methodology for designing similar incentive mechanisms over Proof of Work
consensus algorithms.

##  2\. Related Work

Consensus shares many properties as convergence to Nash equilibria in various
repeated games. Abraham et al. [1] introduced games that share similarities
with the standard consensus problem. We use this work as a motivation for
these ideas.

In addition, there has been ample research into scalability and security-first
protocol designs. Sompolinsky and Zohar showcase the benefit of this approach
in [2, 3, 4] for different tree and DAG based topologies.

##  3\. Background

###  3.1. Consensus Games

We will start with an example of a simple coordination game that motivates the
work of the paper, in that it should incentivize the same response
(consensus). We will extend this game to its infinite form and analyze the
existence of subgame perfect nash equilibria with discounted rewards.

######  Example 3.1.

Suppose that there are $n>1$ players with action space $A_{i}=\\{0,1\\}$.

  * •

If everyone plays 0, then $\forall i\in\mathcal{P},~{}u_{i}(a)=1$ where
$a=(0,0,\dots,0)$.

  * •

If exactly two players $i,j\in\mathcal{P}$ play 1, then
$u_{i}(a)=u_{j}(a)=2,~{}u_{k}(a)=0$ for $k\neq i,j$.

  * •

Otherwise, $\forall i\in\mathcal{P},~{}u_{i}(a)=0$.

From the game above, it is clear that the zero-vector is a pure strategy Nash
equilibrium. No player has a unilateral deviation to choose 1, since all
players including the deviating party will end up with a payoff of 0. However,
two-players who collude and form a deviating coalition have an incentive to
choose 1. To that end, we introduce the concept of resilient Nash equilibria.

######  Definition 3.2.

Let $G$ be a game. A strategy profile $\sigma=(\sigma_{1},\dots,\sigma_{n})$
is a $k$-resilient Nash equilibrium of $G$, if for all coalitions
$C,~{}|C|\leq k$, and all members $i\in C$, the following condition is
satisfied:

$\displaystyle u_{i}(\sigma_{C},\sigma_{-C})\geq
u_{i}(\sigma_{C}^{\prime},\sigma_{-C})$

i.e. coalitions of size at most $k$ do not benefit from deviating [5].

In general, if players are rewarded $\alpha$ for the pure strategy Nash
equilibrium of the zero-vector strategy profile and exactly 2 players are
rewarded with $\beta$ for playing otherwise as above with $\alpha<\beta$,
there will not exist k-resilient Nash equilibria for values of $k$ satisfying
$\frac{2\beta}{k}>\alpha$. From this simple example, we immediately see the
ease and possibility of disrupting consensus that colluding opens up in
economically-based, consensus games.

Now suppose we play this game infinitely many times. We would hope to devise a
strategy that, in the presence of a colluding coalition of size $k$ satisfying
$\frac{2\beta}{k}>\alpha$, is a $k$-resilient subgame perfect Nash
equilibrium. Given that the one-shot game is not $k$-resilient, can we devise
a way to punish this coalition such that consensus at 0 is incentive aligned?
A common, elementary setup in game theory is to find discount factors $\delta$
that incentivize a particular strategy. Although this is unrealistic since
players in the real world have arbitrary $\delta$, this information provides
insight into the dynamics of the game. The strategy that every honest (non-
colluding) player will play is as follows:

  * •

Play 0 if every other player played 0 in the previous round.

  * •

Play 1 if a colluding party of size $k$ deviates to 1 in the previous round
for $t$ rounds.

The cooperation strategy is thus a dominant strategy, subgame perfect nash
equilibrium strategy for the discount factor $\delta$ satisfying:

$\displaystyle\alpha+\delta*\alpha+\delta^{2}*\alpha+\dots$
$\displaystyle\geq\frac{2\beta}{k}+\delta^{t+1}*\alpha+\delta^{t+2}*\alpha+\dots$
$\displaystyle\frac{\alpha}{1-\delta}$
$\displaystyle\geq\frac{2\beta}{k}+\frac{\delta^{t+1}\alpha}{1-\delta}$
$\displaystyle\frac{\alpha}{1-\delta}-\frac{\delta^{t+1}\alpha}{1-\delta}$
$\displaystyle\geq\frac{2\beta}{k}$
$\displaystyle\frac{\alpha}{1-\delta}\big{(}1-\delta^{t+1}\big{)}$
$\displaystyle\geq\frac{2\beta}{k}$
$\displaystyle\frac{1-\delta^{t+1}}{1-\delta}$
$\displaystyle\geq\frac{2\beta}{\alpha k}$

###  3.2. Blockchain Terminology

The important concepts to understand revolve around cryptocurrencies, Proof of
Work (PoW), and Proof of Stake (PoS) protocols. Decentralized cryptocurrencies
most importantly solve the double-spending problem. This is the problem in
which a single user manages to spend the same cryptocurrency in multiple
transactions, a la double spending cryptocurrencies. Since this shouldn’t
happen in any secure financial system, it remains one of the more important
attacks to prevent against.

A PoW system is one in which participants solve some computationally-hard but
tractable puzzle. For our purposes, we are interested in the hashing proof of
work used by cryptocurrency networks. Traditionally in these proof of work
systems, miners deploy massive amounts of computer systems to compete for
rewards. Their computational power provides an accurate distribution over
their expected rewards and their rewards are paid out without an intentional
delay for incentive-compatible reasons (Bitcoin does impose a delay but only
for preventing stale/invalid block rewards).

A PoS system is one in which participants stake the underlying blockchain’s
cryptocurrency to compete for rewards. Rewards should be paid out
proportionally to a miner’s stake. Within these protocols, new attack vectors
are introduced such as the ”Nothing at Stake” problem. Since participants use
money instead of computer power, they can stake their cryptocurrency on every
fork/chain they want, i.e. have nothing at stake for any given chain. To
combat this behavior, we impose slashing conditions on allowed behavior within
a PoS system. When these slashing conditions are satsified, miners lose
portions or the entirety of their stake and so are disincentivized to act a
certain way.

##  4\. Model

Using these concepts as foundations, the synopsis of our model is as follows.
A delayed blockchain protocol is one in which rewards are deterministically or
randomly delayed to provide a staking mechanism on future payouts. We focus
primarily on the notion of double-spending and its potential inclusion within
an active blockchain or DAG protocol. The delayed property enables this to be
overlaid onto any blockchain network, providing increased security through
verifiable fraud proofs. Broadcasting valid fraud proofs will result in a
miner’s future rewards being slashed and eliminated, potentially shared with
the reporter.

######  Definition 4.1.

A fraud proof is an unforgeable, cryptographic proof of misbehavior, submitted
to the protocol that can be verified in polynomial time.

Given that double-spends are verifiably erroneous actions (existence of
conflicting transactions signed by the same private key), we can transform
this into a punishable action. Miners should not attempt to double-spend nor
serve users attempting to; any indication signals malice.

We adopt the original model from Nakamoto in his seminal paper on Bitcoin and
that used by Sompolinsky and Zohar in their work on scalable cryptocurrency
protocols. There is a network of miners, represented by a graph $G=(V,E)$ such
that each miner has some proportion $p_{v}$ of the aggregate power,
$\sum_{v\in V}p_{v}=1$. We will model block inter-arrival times exponentially
and model global block arrivals according to a Poisson process
$\\{N(t)~{}|~{}t\geq 0\\}$ with rate $\lambda$. A miner $v$’s block creation
rate is then $p_{v}*\lambda$. For simplicity, we sum the transaction fee and
block reward into a general reward $\alpha^{(t)}$ for mining new blocks at
time $t$. In addition, we denote $G_{v}^{(t)}=(V^{(t)},E^{(t)})$ as the
network view of miner $v$ at time $t$.

######  Definition 4.2.

Given a cryptocurrency network protocol with reward $\alpha^{(t)}$ and a graph
$G$, a miner $v$ can expect to have, at time $t$ with
$p=(p_{1},\dots,p_{|V|})$ and with cost function $c_{v}^{(t)}(p)$, the utility
function:

$\displaystyle u_{v}^{(t)}(p)$ $\displaystyle=(\alpha^{(t)}*p_{v}*\lambda-
c_{v}^{(t)})dt$

######  Example 4.3.

We begin with a discretized formulation of a delayed mining game. At each
discretized time length $\Delta$ starting from 0, a miner is selected and
rewarded for mining a block. This miner $v$ has a $p_{v}$ chance of mining a
block each time step. Using the equations defined previously, we can quantify
this miner’s expected payout at some future time by simply taking a sum over
the elapsed time steps.

Upon mining a block, the reward is kept frozen for $k$ time steps. This means
that if a miner $v$ mines a block at time $t$, he will receive that reward at
time $t+\Delta*k$. The motivation for this, as we briefly mentioned, is to
ensure that miner’s have stake in the protocol (in their future rewards). In
the interval $[t,t+\Delta*k)$, the miner should be properly incentivized not
to behave maliciously if he hopes to receive the reward. We can additionally
force, as part of the protocol, two additional conditions on participation and
rewards to ensure honest behavior is incentive compatible. While these may not
be intuitive yet, they will make sense later on.

######  Definition 4.4.

A $(k,d,\gamma)$-delayed blockchain or DAG protocol with block and transaction
fee rewards $\alpha^{(\cdot)}$ is a protocol where rewards are timelocked for
$k$ rounds, $d$ aggregate proof of work is required up front separate from the
underlying mining process, and $\alpha^{(\cdot)}$ decays with exponential rate
$\gamma$.

Note: $(k,0,0)$-delayed protocols mimic existing protocols — $k=100$ for
Bitcoin and $k=0$ for others.

The first two parameters are simple and easily understood as the length of
delay in future rewards (which can capture arbitrarily many future rewards)
and the startup cost to combat Sybil attacks, respectively. The third
parameter, $\gamma$, incentivies miners to ”stick around” and actively mine or
face arbitrary rates of decay in their future, discounted rewards.

######  Proposition 4.5.

In a $(k,d,\gamma)$-delayed protocol with block and transaction fee rewards
$\alpha^{(\cdot)}$, timestep lengths $\Delta$, and discount factor $\delta$,
it is expected that the utility a miner $v$ has at each round from time $t$
is:

$\displaystyle\mathbb{E}_{k,\gamma}[u_{v}^{((t,t+\Delta))}]=\delta^{k}\Delta(\alpha^{(t)}*e^{-\gamma*\Delta*k}*p_{v}*\lambda-
c_{v}^{(t)})$

Note: We will want to find values of $\delta$ such that our enhanced protocol
benefits from greater security guarantees as indicated by the potential loss
in payouts that come from malicious behavior.

##  5\. Delayed Blockchains

Recall that the goal of these changes is to provide increased security and
incentive compatibility to arbitrary protocol designs. We want to prevent
against double-spend attacks from large mining parties up to a majority.
Currently, the state of the art in Proof of Work protocol design has no
punishment capabilities by design. Rewards are paid out more or less
instantly; delays are not used to incentivize honest behavior but as a check
on stale blocks.

In blockchain networks, we also have access to a robust public/private key
infrastructure. Actions by mining participants in the network are uniquely
signed by participants’ private keys. If we hope to punish malicious
participants, we would hope to ”blacklist”/punish their public identities
(public keys) within the protocol. In the current iteration of public
blockchains however, this suffers from the following drawbacks.

###  5.1. Drawbacks of existing protocols

  1. (1)

Creating new public/private key pairs or identities is trivial. Malicious
miners can continuously change to a newly generated identity.

  2. (2)

Payouts are instantaneous. Assuming a particular chain is not reverted, large
mining parties can withdraw funds immediately.

  3. (3)

Large parties do not have proportional ”skin in the game” or stake against
their mining power.

For the purpose of this paper, we address the three issues above. The
usefulness of a $(k,d,\gamma)$-delayed blockchain protocol allows us the
ability to tune the severity of the punishment to arbitrary strengths in order
to combat the mitigation techniques above. The intuition for each is as
follows:

  1. (1)

If $d>>0$, creating new public/private key pairs to behave maliciously with
old key pairs should be disincentivized. In addition, if $\gamma$ grows
exponentially as a function of the number of times a past winning miner drops
out of the current miner set, past winners will lose substantial portions of
their future rewards. In many cases, $\gamma$ will incentivize sticking around
for sufficiently large $k$ such that $d$ can be set to 0.

  2. (2)

Payouts are no longer instantaneous and miners cannot instantly withdraw funds
until they honestly cooperate with the protocol rules for a parameterized
amount of time.

  3. (3)

Miners have stake in reporting malicious behavior and in behaving according to
the protocol.

##  6\. Subgame Perfect Equilibria

As we showed in our toy example, there are lengths of time for which
deviations are not rational decisions. We operate strictly in a rational agent
model and leave notions of Byzantine or irrational behavior for future work.
Towards similar results, we consider a double-spend deviation on a
$(k,d,\gamma)$-delayed blockchain with deviation payoff $\epsilon>0$. That is,
an adversary can double-spend and receive an arbitrarily large reward of
$\epsilon$. We would expect that a double-spend attempt should only be a
rational deviation if $\epsilon$ is greater than the aggregate payout of a
miner’s future rewards.

###  6.1. $(k,0,\gamma)$-delayed

For simplicity we assume there is no cost to mining or Sybil startup cost. We
also assume that all miners have been playing for sufficiently long. The
expected payoff for a miner $v$ with power $p_{v}$ and discount factor
$\delta$, who has honestly participated in the protocol for $l>>k$ time steps
is:

$\displaystyle
u_{v}^{(1:l)}(p)=\sum_{i=1}^{l}\delta^{k+i-1}(\alpha*e^{-\gamma*k}*p_{v}*\lambda)$

If the payoff for double-spending is $\epsilon$. Then the payoff for double
spending after $l$ rounds in the infinitely repeated game can be represented
by replacing the last $k$ expected payoffs with $\epsilon$. This is because we
assume another miner submits a fraud proof and slashes the $k$ most recent,
expected payouts:

$\displaystyle u_{v}^{(1:l-k)}(p)+\epsilon+u_{v}^{(l:\infty)}(p)$

Then it follows, a profitable attack would satisfy the following:

$\displaystyle u_{v}^{(1:\infty)}(p)$ $\displaystyle\leq
u_{v}^{(1:l-k)}(p)+\epsilon+u_{v}^{(l+1:\infty)}(p)$ $\displaystyle
u_{v}^{(l-k+1:l)}(p)$ $\displaystyle\leq\epsilon$
$\displaystyle\sum_{i=l-k+1}^{l}\delta^{k+i-1}(\alpha*e^{-\gamma*k}*p_{v}*\lambda)$
$\displaystyle\leq\epsilon$ $\displaystyle\epsilon$
$\displaystyle=O(k*\alpha*\delta^{k}*e^{-\gamma*k}*\lambda)$

We arrive at the big-O form using a rudimentary simplification of the left-
hand sum. We know that $\delta\in(0,1)$, therefore, for
$l>>k,~{}\delta^{l}<\delta^{k}$. Each term of the left-hand sum has a
$\delta^{l^{\prime}},~{}l^{\prime}\geq l$ and so is bounded by $\delta^{k}$.
The sum is taken over $k$ terms, so we add a factor of $k$ in front.
Additionally, since $p_{v}\in[0,1]$, it follows that its omission can only add
to the growth of the right-hand term.

If $\epsilon=O(k*\delta^{k}*e^{-\gamma*k})$, then a double-spend attack should
be a profitable deviation; strict equality would indicate a guaranteed profit.
Given we set $d=0$, there is no cost to getting punished and malicious miners
can trivially jumpstart mining on new public/private key pairs. Now, if we
increase $d>0$, the cost of the double spend will increase. This, however, has
no effect on the payoff of honest participation. Therefore, for $\epsilon$
sufficiently large, the protocol designer can tune $d$ to push attack costs
higher.

To analyze subgame perfect equilbria, we must reverse the inequality. We leave
the equations unsimplified and closed forms for future work. These bounds
serve to illustrate the various ways we can increase attack costs without
altering honest rewards.

###  6.2. $(k,d,\gamma)$-delayed

Now consider the case where $d>>0$. For a given miner $v\in V$ with power
fraction $p_{v}$, we let $r_{v}^{d}$ denote the random variable of the total
number of rounds (resp. time interval length) of the blockchain protocol that
it takes miner $v$ to solve $d$ proof of work. It follows that
$\mathbb{E}_{v,d}[r^{d}_{v}]<\infty$, since proofs of work for hashing live in
a finite space.

Now, when an attacker $v$ double-spends, their address is invalidated or
”blacklisted” by the protocol’s rules. In order to startup again, the attacker
$v$ generates a clean public/private key pair and shifts $p_{v}$ to this new
pair. The miner $a$ must complete $d>>0$ proof of work before earning any
rewards. Then it is only profitable to do so if the following is satisfied:

$\displaystyle u_{v}^{(1:\infty)}(p)$ $\displaystyle\leq
u_{v}^{(1:l-k)}+\epsilon+u_{v}^{(l+r_{v}^{d}+1:\infty)}(p)$ $\displaystyle
u_{v}^{(l-k+1:l+r_{v}^{d})}$ $\displaystyle\leq\epsilon$
$\displaystyle\sum_{i=l-k+1}^{l+r_{v}^{d}}\delta^{k+i-1}(\alpha*e^{-\gamma*k}*p_{v}*\lambda)$
$\displaystyle\leq\epsilon$ $\displaystyle\epsilon$
$\displaystyle=O((k+r_{v}^{d})*\alpha*\delta^{k}*e^{-\gamma*k}*\lambda)$

With this, we only increase the cost of a successful double-spend attack.
Since honest, long-lived miners are rewarded with only needing to solve the
startup proof of work once, they benefit in the long run. The right balance
between tuning these parameters would be an assignment that reaches a balance
between the value of future discounted rewards and the cost of successfully
executing a double-spend attack.

##  7\. $\gamma$ selection

Using $\gamma$ as intended would require protocol upgrades. If at any time
$t$, we have a view of all miners or stakers by a list of public/private key
identities $pks^{(t)}=\bigoplus_{v\in V^{(t)}}pk_{v}$, then as long as the
winner $v^{*}$ at time $t$ continues to actively mine for $\Delta*k$ more time
steps, they can expect their future reward to decay more slowly or not at all
compared to the event that they stop any time before the delayed interval has
passed.

More generally, $\gamma$ could be parameterized to the frequency of
participation of a particular miner. Newly generated addresses will experience
fast decay in their future rewards compared to incumbent, ”reputable”
addresses. Short-lived miners can be penalized for their undesirable behavior,
while long-lived nodes can be incentivized through proper $\gamma$ selection.
In any of these distributed systems, we want to incentivize long-lived
participation and truthful participation. Imposing restrictions on the
behavior the protocol designer desires allows the designer control of the
underlying protocol’s incentives.

##  8\. Implementation

Without detailing exactly how these ideas can be implemented, we offer a
variety of high-level techniques. For a $(k,d,\gamma)$-delay implementation,
we can extend the mining protocol to include timelocked transactions for
winners of the mining game, parameterized by a length $k$. The underlying
protocol can maintain a set $pks^{(t)}$ at each time $t$ and track a variety
of information about all miners it has seen in the past (miners can reach
consensus on this dataset as well) for $\gamma$ funtionality. Additionally, a
double proof of work layer can be added to the traditional mechanics to
include functionality of the startup cost, $d$, parameter.

##  9\. Conclusion

In this paper, we presented a new technique for improving the security of any
Proof of Work blockchain/DAG protocol. The main technique involves delaying
the rewards of miners to create a Proof of Stake style staking mechanism. We
impose slashing conditions around fraud proofs that can be determined by
protocol designers. By slashing future rewards, we simulate slashing a miner’s
stake in the system.

## References

  * [1] Ittai Abraham, Lorenzo Alvisi, and Joseph Y Halpern.  Distributed computing meets game theory: combining insights from two fields.  Acm Sigact News, 42(2):69–76, 2011.
  * [2] Yonatan Sompolinsky and Aviv Zohar.  Bitcoin’s security model revisited.  arXiv preprint arXiv:1605.09193, 2016.
  * [3] Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar.  Spectre: A fast and scalable cryptocurrency protocol.
  * [4] Yonatan Sompolinsky and Aviv Zohar.  Phantom.
  * [5] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani.  Algorithmic game theory, volume 1.  Cambridge University Press Cambridge, 2007.