Unambiguity and Fewness for Nonuniform Families of Polynomial-Size
Nondeterministic Finite Automata111This work corrects and also significantly
alters the preliminary report that appeared in the Proceedings of the 16th
International Conference on Reachability Problems (RP 2022), Kaiserslautern,
Germany, October 17–21, 2022, Lecture Notes in Computer Science, vol. 13608,
pp. 77–92, Springer Cham, 2022.

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

###### Abstract

Nonuniform families of polynomial-size finite automata, which are series of
indexed finite automata having polynomially many inner states, are used in the
past literature to solve nonuniform families of promise decision problems.
Among such nonuniform families of finite automata, we focus our attention, in
particular, on the variants of nondeterministic finite automata, which have at
most “one” (unambiguous), “polynomially many” (few) accepting computation
paths, or unambiguous/few computation paths leading to each fixed
configuration. When such machines are limited to make only one-way head moves,
we can prove with no unproven hardness assumptions that some of these variants
are different in computational power from each other. As for two-way machines
restricted to instances of polynomially-bounded length, families of two-way
polynomial-size nondeterministic finite automata are equivalent in power to
families of polynomial-size unambiguous finite automata.

Key words nonuniform state complexity, finite automata, accepting computation
path, unambiguous, fewness

##  1 Historical Background and Quick Overview

As an introduction, we briefly go over its historical background and then take
a quick overview of the major contributions of this work.

###  1.1 Unambiguity and Fewness in Complexity Theory

The number of accepting computation paths of an underlying nondeterministic
machine has been a centerpiece of intensive research over the decades because
the acceptance criteria of how the machine “accepts” each instance are of
great importance for nondeterministic computation and this is indeed a key to
the full understandings of nondeterministic computation.

Among various acceptance criteria, the notion of _unambiguity_ for an
underlying nondeterministic machine, which means at most one accepting
computation path, has drawn a great interest. The study of unambiguous
context-free languages, for example, is one of the important subjects in
formal language theory because there exist practical parsing algorithms for
those languages.

In computational complexity theory, the unambiguity issues have been discussed
since Valiant [19] introduced the unambiguous polynomial-time complexity
class, known as $\mathrm{UP}$, in connection to the existence of one-way
functions, which play an essential role in modern cryptography. When we allow
more than one accepting computation paths but limited to “few” (i.e.,
polynomially many) paths, we then obtain the complexity class called
$\mathrm{FewP}$, introduced in [1, 2]. It follows that
$\mathrm{P}\subseteq\mathrm{UP}\subseteq\mathrm{FewP}\subseteq\mathrm{NP}$;
however, it still remains open whether or not these inclusions are proper. A
series of papers in the past literature further proposed various refinements
of unambiguous languages and that has enriched the study of computational
complexity of languages. Unarguably, the study on the behaviors of
nondeterministic machines producing a various number of accepting computation
paths is a key in computational complexity theory to the anticipated
separation between $\mathrm{P}$ and $\mathrm{NP}$.

For the model of space-bounded machines, on the contrary, the logarithmic-
space (or log-space, for short) analogues of $\mathrm{UP}$ and
$\mathrm{FewP}$, denoted $\mathrm{UL}$ and $\mathrm{FewL}$, were discussed in
the 1990s [5] using nondeterministic logarithmic-space computations in
comparison with the polynomial-time computations. The memory space restriction
sometimes presents a quite different landscape from the runtime restriction.
For instance, whereas $\mathrm{NP}$ and $\mathrm{co}\mbox{-}\mathrm{NP}$ are
not known to coincide, their log-space counterparts, $\mathrm{NL}$ and
$\mathrm{co}\mbox{-}\mathrm{NL}$, are in fact equal [8, 18].

With the help of Karp-Lipton style advice [13], Reinhardt and Allender [16],
for instance, managed to prove the equivalence between
$\mathrm{NL}/\mathrm{poly}$ and $\mathrm{UL}/\mathrm{poly}$ although
$\mathrm{NL}$ and $\mathrm{UL}$ themselves are still unknown to coincide,
where advice is an external information source, provided to an underlying
Turing machine in parallel to a standard input in order to enhance its
computational power. This equivalence is not yet known between $\mathrm{NP}$
and $\mathrm{UP}$.

Bourke, Tewari, and Vinodchandran [4] and lately Pavan, Tewari, and
Vinodchandran [15] introduced another intriguing refinement of the
aforementioned complexity classes associated with unambiguity and fewness
notions, and they exhibited among such refined complexity classes the
existence of a rich structure situated in between $\mathrm{L}$ and
$\mathrm{NL}$. Their refined classes include: $\mathrm{ReachUL}$,
$\mathrm{ReachFewL}$, $\mathrm{ReachLFew}$, and $\mathrm{FewUL}$. It is also
imperative to expand and explore the nature of unambiguity and fewness of
accepting computation paths in other computational models. As such a model, we
consider nonuniform finite automata families.

###  1.2 Nonuniform Families of Polynomial-Size Finite Automata

Let us turn our attention to “finite(-state) automata”, which are one of the
simplest models of computation. Those machines have been intensively studied
since its early introduction but, only since the late 1970s, “nonuniform
families” of those machines have drawn our attention. In analogy to Boolean
circuit families, Berman and Lingas [3] and Sakoda and Sipser [17] studied
nonuniform families of finite automata, indexed by natural numbers, of
polynomial state complexity. Such a finite automata family is succinctly said
to have _polynomial size_. A series of papers [7, 9, 10, 11, 12, 21, 22, 23,
24, 27] have since then made crucial contributions to establishing a coherent
theory over _nonuniform polynomial state complexity_ of families of
“languages”, more generally, _promise decision problems_. Nonuniform machine
families are generally used as a vehicle to solve those families of promise
problems in quite efficient ways. In such a nonuniform setting, there are two
parameters to take into consideration: machine’s index $n$ and input length
$|x|$. The notion of nonuniformity, ranging from advice-enhanced Turing
machines to families of Boolean circuits, is as important as that of
uniformity in computational complexity theory.

A family of finite automata can be viewed as an analogue of a family of
Boolean circuits but it is quite different in the following key point: while
each circuit in a circuit family takes only inputs of a fixed length, a finite
automaton in an automata family can take inputs of arbitrary length. This
makes it possible for us to discuss subfamilies of an automata family by
freely restricting the size of inputs, which is called a “ceiling” [24]. By
choosing different ceilings, we can discuss the computational complexity of a
wide variety of nonuniform families of finite automata.

The collection of families of promise decision problems that are solvable by
nonuniform families of polynomial-size two-way deterministic finite automata
is particularly denoted $2\mathrm{D}$, and its nondeterministic variant is
denoted $2\mathrm{N}$ [17]. These automata families in the above-mentioned
literature have been studied in direct connection to logarithmic-space advised
complexity classes, such as $\mathrm{L}/\mathrm{poly}$ and
$\mathrm{NL}/\mathrm{poly}$ [3, 11]. More precisely, we denote by
$2\mathrm{D}/\mathrm{poly}$ and $2\mathrm{N}/\mathrm{poly}$ the restrictions
of $2\mathrm{D}$ and $2\mathrm{N}$ on only instances having polynomial
ceilings. It was proven that the collapse of $2\mathrm{N}/\mathrm{poly}$ to
$2\mathrm{D}/\mathrm{poly}$ occurs exactly when $\mathrm{NL}/\mathrm{poly}$
equals $\mathrm{L}/\mathrm{poly}$. A similar connection was observed in [21]
between families of restricted nondeterministic finite automata and the so-
called _linear space hypothesis_ , proposed in [26].

When underlying finite automata are limited to make only one-way head moves,
complexity classes of promise problem families present us a quite different
landscape. For the one-way analogues of $2\mathrm{D}$ and $2\mathrm{N}$,
denoted respectively by $1\mathrm{D}$ and $1\mathrm{N}$, it was proven that
$1\mathrm{D}\neq 1\mathrm{N}\neq\mathrm{co}\mbox{-}1\mathrm{N}$ [17].

In fact, the nonuniform nature of automata families provides enormous
flexibility to solving families of promise problems. Manifestation of this
fact has been demonstrated in the field of automata theory for various machine
types, including deterministic, nondeterministic, probabilistic, alternating,
quantum automata and also pushdown automata in the literature.

It has been expected to further expand the scope of the study on nonuniform
polynomial state complexity theory to other types of polynomial-size finite
automata families.

###  1.3 New Challenges and Main Contributions

The _theory of nonuniform polynomial state complexity_ has not been well
developed in depth and in scope. It is therefore imperative to replenish this
theory by cultivating and examining structural properties of underlying finite
automata and their nonuniform families. In this work, we intend to explore
such structural properties of We modify the existing models of nonuniform
families of nondeterministic finite automata by requiring various restrictions
on their computation paths. For this purpose, we wish to adapt various notions
of [15] associated with unambiguity and fewness notions to fit into our
setting of nonuniform families of finite automata. Our intension here is to
replenish the theory by making new challenges in the topics of unambiguity and
fewness for polynomial-size families of finite automata, because unambiguity
and fewness are in fact important notions in automata theory. Therefore, we
wish to explore these notions founded on nonuniform families of
nondeterministic finite automata. In particular, we attempt to follow the
aforementioned work of Pavan et al. [15] in our setting of nonuniform state
complexity theory. For this purpose, we wish to identify state complexity
classes as done in the logarithmic-space setting of [15]. We intend to study
the computational complexity of families of polynomial-size nondeterministic
finite automata that satisfy various conditions on accepting computation
concerning unambiguity and fewness.

In a spirit similar to [15], we will introduce six nonuniform polynomial state
complexity classes between $1\mathrm{D}$ and $1\mathrm{N}$ in Section 3.1 and
between $2\mathrm{D}$ and $2\mathrm{N}$ in Section 4. We will then demonstrate
various relationships among those nonuniform complexity classes and their
complement classes. In the case of one-way models, in particular, we will
prove separations among some of these complexity classes _with no unproven
hardness assumptions_. In the case of two-way models, on the contrary, we will
demonstrate the collapses of complexity classes by exploiting a close relation
between nonuniform families of polynomial-size finite automata having
polynomial ceilings and logarithmic-space advised computation. It was remarked
in [27] that there is a close connection between nonuniform families of
polynomial-size finite automata and one-tape linear-time Turing machines, in
particular, between promise problem families in $1\mathrm{C_{=}}$ and
languages in $\mathrm{1\mbox{-}C}_{=}\mathrm{LIN/lin}$. We will adapt such a
close connection and exploit it to prove the desired separations of this work.
Our result is summarized and illustrated in Figure 1. The detailed explanation
of the complexity classes in the figure will be given in Sections 3.1 and 4.

Figure 1: Inclusion and collapse relations among families of promise problems
discussed in this work except for
$1\mathrm{N}\neq\mathrm{co}\mbox{-}1\mathrm{N}$ [17] and $1\mathrm{D}\neq
1\mathrm{U}\neq\mathrm{co}\mbox{-}1\mathrm{U}$ [27].

##  2 Basic Notions and Notation

We will explain the foundation of this work: finite automata models of
polynomial state complexity.

###  2.1 Numbers, Promise Problems, and Kolmogorov Complexity

Let $\mathbb{N}$ (resp., $\mathbb{N}^{+}$) denote the set of all nonnegative
(resp., positive) integers. Notice that
$\mathbb{N}=\mathbb{N}^{+}\cup\\{0\\}$. Given two integers $m$ and $n$ with
$m\leq n$, $[m,n]_{\mathbb{Z}}$ denotes the _integer interval_
$\\{m,m+1,m+2,\ldots,n\\}$. When $n\in\mathbb{N}^{+}$, $[1,n]_{\mathbb{Z}}$ is
abbreviated as $[n]$ for simplicity. Given a set $A$, the notation $\|A\|$
denotes the _cardinality_ of $A$ and ${\cal P}(A)$ denotes the _power set_ of
$A$.

A _polynomial_ in this paper is assumed to have nonnegative integer
coefficients. An _exponential_ refers to a function of the form $2^{p(n)}$ for
an appropriate polynomial $p$. Any _logarithm_ is assumed to take the base 2
and any _logarithmic function_ $f$ has the form $a\log x+b$ for certain
constants $a,b\geq 0$. For convenience, we say that a function $f$ on
$\mathbb{N}$ (i.e., from $\mathbb{N}$ to $\mathbb{N}$) _super-exponential_ if,
for any polynomial $p$, $f(n)>2^{p(n)}$ holds for all but finitely many
numbers $n\in\mathbb{N}$. In contrast, a function $f$ is _sub-exponential_ if
there exists a constant $\alpha\in[0,1)$ satisfying $f(n)\leq 2^{n^{\alpha}}$
for all but finitely many numbers $n\in\mathbb{N}$.

An _alphabet_ is a finite nonempty set of “symbols” or “letters”. Given such
an alphabet $\Sigma$, a _string_ over $\Sigma$ refers to a finite sequence of
symbols in $\Sigma$. The length of this sequence is called the _length_ of the
string. In particular, the _empty string_ is a unique string of length $0$ and
is denoted by $\varepsilon$.

We briefly explain (nonuniform) families of promise (decision) problems as
described in [21, 22, 23, 24, 27]. Given an alphabet $\Sigma$, a _promise
(decision) problem over $\Sigma$_ is a pair $(A,B)$ of sets satisfying $A\cup
B\subseteq\Sigma^{*}$ and $A\cap B=\varnothing$. Instances in $A$ are called
_positive_ (or YES-instances) and instances in $B$ are _negative_ (or NO-
instances). To clarify the use of positive/negative instances, we often use
the superscripts of $(+)$ and $(-)$ to express a promise problem as
$(L^{(+)},L^{(-)})$. We further consider a family ${\cal L}$ of promise
problems $(L_{n}^{(+)},L_{n}^{(-)})$ for all indices $n\in\mathbb{N}$;
however, we focus only on families of promise problems over the “same”
alphabet333In [9, 10, 11, 12], this extra condition is not required. $\Sigma$.
We consider a family ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of those promise
problems. From this requirement, we often denote the union $L_{n}^{(+)}\cup
L_{n}^{(-)}$ by $\Sigma_{n}$ whereas the notation $\Sigma^{n}$ is reserved for
the set of strings of length $n$. Any string in $\Sigma_{n}$ indicates a
_valid_ (or a _promised_) instance over $\Sigma$. The _complement_ of ${\cal
L}$, denoted $\mathrm{co}\mbox{-}{\cal L}$, consists of
$(L_{n}^{(-)},L_{n}^{(+)})$ for all indices $n\in\mathbb{N}$.

Let $U$ denote any universal (deterministic) Turing machine taking binary
input strings and eventually produces binary output strings. Given any binary
strings $x$ and $y$, the _conditional Kolmogorov complexity of $x$ conditional
to $y$_, denoted $C(x|y)$, is the length of the shortest binary string $p$
such that $U$ on inputs $(p,y)$ produces $x$ on its output tape. We use the
notation $\varepsilon$ to denote the _empty string_. If $y$ is $\varepsilon$,
we write $C(x)$ instead of $C(x|\varepsilon)$. This is referred to as the
_(unconditional) Kolmogorov complexity of $x$_. For more detail, the reader
refers to a textbook, e.g., [14].

###  2.2 Families of Finite Automata

Throughout this work, we mostly deal with a computational model of
nondeterministic finite automata. For convenience, we freely abbreviate a
_one-way nondeterministic finite(-state) automaton_ as a 1nfa and a _two-way
nondeterministic finite(-state) automaton_ as a 2nfa. Similarly, we call
deterministic variants of 1nfa and 2nfa by 1dfa and 2dfa, respectively.

Our main target is “families” of finite automata of the same machine type over
the same alphabet $\Sigma$. In particular, we use families of 2nfa’s (as well
as 2dfa’s, 1nfa’s, and 1dfa’s), indexed by natural numbers, as a base model to
solve families of promise problems.

Each 2nfa $M_{n}$ in such a family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ is
equipped with a semi-infinite input tape, whose tape cells are indexed by
natural numbers starting with $0$. Formally, $M_{n}$ is expressed as a
septuple
$(Q_{n},\Sigma,{\\{\rhd,\lhd\\}},\delta_{n},q_{0,n},Q_{acc,n},Q_{rej,n})$ with
two designated endmarkers $\rhd$ and $\lhd$ and two sets $Q_{acc,n}$ and
$Q_{rej,n}$ of accepting (inner) states and rejecting (inner) states
satisfying both $Q_{acc,n}\cup Q_{rej,n}\subseteq Q_{n}$ and $Q_{acc,n}\cap
Q_{rej,n}=\varnothing$. Any inner state in $Q_{acc,n}\cup Q_{rej,n}$ are
simply called a _halting (inner) state_. The transition function $\delta$ is
defined only on non-halting states. with a finite set $Q$ of inner states, an
alphabet $\Sigma$ with two designated endmarkers $\rhd$ and $\lhd$, a
transition function $\delta:(Q-Q_{halt})\times\check{\Sigma}\to{\cal
P}(Q\times D)$, the initial inner state $q_{0}$ ($\in Q$), and two sets
$Q_{acc}$ and $Q_{rej}$ of accepting states and rejecting states with
$Q_{acc}\cup Q_{rej}\subseteq Q$ and $Q_{acc}\cap Q_{rej}=\varnothing$, where
$Q_{halt}=Q_{acc}\cup Q_{rej}$, $\check{\Sigma}=\Sigma\cup\\{{\rhd,\lhd}\\}$,
and $D=\\{-1,0,+1\\}$. Any transition $(p,d)\in\delta(q,\sigma)$ indicates
that, in a single step, $M$ scans $\sigma$, changes its inner state from $q$
to $p$, and move its tape head in direction $d$ (i.e., $-1$ means “to the
left”, $+1$ means “to the right”, and $0$ means “staying still”). The _state
complexity_ of $M_{n}$ refers to $|Q_{n}|$, which is the total number of
$M_{n}$’s inner states, and it is briefly denoted $sc(M_{n})$. A family ${\cal
M}$ is said to have _polynomial size_ if there exists a polynomial $p$ such
that $sc(M_{n})\leq p(n)$ holds for all $n\in\mathbb{N}$. For more information
on the underlying setting of automata families, the reader refers to [24].

In contrast, one-way models of 2nfa’s and 2dfa’s, which are called 1nfa’s and
1dfa’s, take transition function of the form
$(Q-Q_{halt})\times\check{\Sigma}\to{\cal P}(Q)$ and
$(Q-Q_{halt})\times\check{\Sigma}\to Q$, respectively. Following [24], a one-
way finite automaton is always assumed to make no stationary move (or
$\varepsilon$-move); that is, its tape head must move only in one direction,
to the right, whenever it reads an input symbol (including the endmarkers).
This condition is sometimes called _real time_ in the literature. If $M$ is
further allowed to make any $\varepsilon$-move, then we use the specific term
“1.5-way”. See Section 5 for a further discussion.

It is imperative to clarify a few important terminologies associated with
“computation” of finite automata $M_{n}$ on input $x$. We fix an input
arbitrarily and consider all surface configurations of each (either one-way or
two-way) machine $M_{n}$ on the input $x$. A _surface configuration_ of
$M_{n}$ on $x$ is of the form $(q,i)$ in $Q\times[0,|x|+1]_{\mathbb{Z}}$
excluding $x$, which indicates that $M_{n}$ is in inner state $q$ and its tape
head is located at cell $i$, assuming that tape cells are indexed by
nonnegative integers and that $\rhd$ and $\lhd$ are placed respectively at
cell $0$ and cell $|x|+1$. In the rest of this work, since we deal only with
surface configurations, we drop the word “surface” altogether from “surface
configurations”. With the use of configurations, we consider a _computation
graph_ of $M_{n}$ on $x$, whose vertices are configurations of $M_{n}$ on $x$
and a transition from any non-halting configuration to another configuration
forms a directed edge. We write $(p,i)\vdash(q,i+1)$ to express an edge of
this graph. An _accepting configuration_ is a configuration with an accepting
(inner) state. Similarly, a _rejecting configuration_ is defined with the use
of a rejecting (inner) state. A _computation path_ is a path in a computation
graph from the root (i.e., the initial configuration) to a certain leaf (i.e.,
a halting configuration) if any. A computation path is _accepting_ (resp.,
_rejecting_) if it ends in a configuration with an accepting (resp., a
rejecting) configuration.

We say that $M_{n}$ _halts_ on $x$ if there exists a computation path of
finite length in the computation graph of $M_{n}$ on $x$. In this work, we are
interested only in finite automata that always halt on all valid instances.
For such a halting 2nfa $M_{n}$, we say that $M_{n}$ _accepts_ $x$ if $M_{n}$
starts with $\rhd x\lhd$ and produces at least one accepting computation path,
and $M$ is said to _reject_ $x$ otherwise.

Let us consider a family ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of promise problems over
a fixed alphabet $\Sigma$. The set $\Sigma_{n}$ is a set of _valid_ instances
in $\Sigma^{*}$. Recall that $\Sigma_{n}$ expresses the set of all valid (or
promised) instances over $\Sigma$ for $(L_{n}^{(+)},L_{n}^{(-)})$. For any
other “invalid” instance $x$, when a machine, say, $M_{n}$ takes $x$ as an
input, we do not require any condition on the behavior of the machine. A
family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of machines over $\Sigma$ is
said to _solve_ (or _recognize_) ${\cal L}$ if, for any $n\in\mathbb{N}$, (1)
for any $x\in L_{n}^{(+)}$, $M_{n}$ accepts $x$ and (2) for any $x\in
L_{n}^{(-)}$, $M_{n}$ rejects $x$. There may be a case where $M$ does not even
halt on invalid instances.

The notation $2\mathrm{N}$ (resp., $1\mathrm{N}$) denotes the collection of
all families of promise problems solved by appropriate families of polynomial-
size 2nfa’s (resp., polynomial-size 1nfa’s). Similarly, the notation
$2\mathrm{D}$ (resp., $1\mathrm{D}$) is defined using 2dfa’s (resp., 1dfa’s).

Given an input $xy$, we say that a one-way tape head _crosses_ a boundary
between $x$ and $y$ in inner state $q$ if
$(q_{0},0)\vdash^{*}(p,|\\!\rhd\\!x|)\vdash(q,|\\!\rhd\\!x|+1)$ for a certain
$p\in Q_{n}$. A _boundary_ is a border between two consecutive tape cells on a
tape. The boundary between cells $t-1$ and $t$ is called boundary $t$. A move
of a tape head is split into two actions: (i) $M$ reads a tape symbol, (ii) it
changes its inner state, and (iii) it moves its tape head to an adjacent cell.
When the tape head move to the next cell, it must cross a boundary with an
updated inner state.

_Boundary $0$_ is the left border of cell $0$. For any $t\in\mathbb{N}^{+}$,
_boundary $t$_ refers to the border between the two cells indexed $t-1$ and
$t$. Assume that $M$ returns its tape head back to the start cell and halts. A
_crossing sequence at boundary $t$_ is a series
$(q_{i_{1}},q_{i_{2}},\ldots,q_{i_{2k}})$ of inner states such that (i) $M$
first crosses the boundary $t$ from left to right with inner state
$q_{i_{1}}$, (ii) at the $2j$th ($j\in[k]$) turn, $M$ crosses boundary $t$
from right to left with inner state $q_{i_{2j}}$, and (iii) at the $(2j+1)$th
turn, $M$ crosses boundary $t$ from left to right with inner state
$q_{i_{2j+1}}$. Note that every computation path produces a unique series
$(\gamma_{0},\gamma_{1},\gamma_{2},\ldots)$ of crossing sequences $\gamma_{t}$
at each boundary $t$.

We show a technical but useful lemma for 2nda’s by an argument similar to
[11]. We assume that all machines in this work make their tape head return to
the start cell and halt.

Given a 2nfa $M$ and an input $x$, we define a specific computation path
$\gamma_{M}(x)$ as follows. Let $\gamma_{M}(x)$ be the shortest accepting
computation path of $M$ on input $x$ if $M$ accepts $x$, and let
$\gamma_{M}(x)$ be the shortest rejecting computation path of $M$ on $x$. For
convenience, this computation path $\gamma_{M}(x)$ is called a _critical path_
of $M$ on $x$.

In general, when $\gamma$ is a crossing sequence of the form
$(q_{i_{1}},q_{i_{2}},\ldots,q_{i_{m}})$, inner state $q_{i_{j}}$ ($j\in[m]$)
is said to _appear at location $j$ in $\gamma$_. For an inner state $q$, we
say that $q$ _behaves identically at two locations in $\gamma$_ if $q$ appears
at two different locations, say, $l_{1}$ and $l_{2}$ in $\gamma$, and $l_{1}$
and $l_{2}$ are both either even or odd. An example of such a case is
$\gamma=(q_{1},q_{3},q_{2},q_{4},q_{1},q_{5})$, where $q_{1}$ behaves
identically at locations $1$ and $5$ in $\gamma$.

###### Lemma 2.1

Let $M$ be any 2nfa. Let $x$ be any string. For any boundary $t$, the crossing
sequence $\gamma_{M}(x)$ at boundary $t$ is upper-bounded by $2sc(M)$.

###### Proof.

Let $M=(Q,\Sigma,\\{\rhd,\lhd\\},\delta,q_{0},Q_{acc},Q_{rej})$ and let $x$ be
any input in $\Sigma^{*}$. Consider the critical path $\gamma_{M}(x)$ of $M$
on the input $x$.

Consider a boundary $t$ and a crossing sequence $\tau_{t}$ at the boundary $t$
on the computation path $\gamma_{M}(x)$. This crossing sequence $\tau_{t}$ has
length at most $2|Q|$ because, otherwise, there exists an inner state $q\in Q$
that behaves identically at two different locations, say, $l_{1}$ and $l_{2}$
in $\gamma_{M}(x)$, and thus we can remove all entries in $\tau_{t}$ between
$l_{1}$ and $l_{2}$ and form a shorter computation path whose outcome is the
same as $\gamma_{M}(x)$. This is a contradiction against the shortest
condition of $\gamma_{M}(x)$. ∎

It is useful to recall the _branching normal form_ from [27]. A 1nfa $N$ is in
the branching normal form if (1) $N$ makes exactly $c$ nondeterministic
choices at every step and (2) $N$ produces exactly $c^{|\triangleright
x\triangleleft|}$ computation paths on all inputs $x$ together with two
endmarkers, where $c$ is an appropriately chosen constant in $\mathbb{N}^{+}$.

######  Lemma 2.2 (branching normal form [27])

Let $M$ be any 1nfa solving a promise problem $(L^{(+)},L^{(-)})$. There
exists another 1nfa $N$ such that $N$ is in a branching normal form and
$sc(N)\leq 3sc(M)+1$.

###  2.3 Unambiguous and Few Computation Paths

Unambiguous and few computation paths of nondeterministic machines have played
an important role in computational complexity theory. Following early works of
[2, 5, 15, 19], we introduce key notions related to “unambiguity” and
“fewness” into the theory of nonuniform polynomial state complexity. Let us
recall from Section 2.2 that any 1nfa (including 1dfa’s) is allowed to have
multiple accepting states and multiple rejecting states. Let ${\cal
M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ denote any family of (one-way or two-way)
nondeterministic finite automata.

  * $\circ$

Firstly, ${\cal M}$ is called _unambiguous_ if, for each index
$n\in\mathbb{N}$ and for any input $x\in\Sigma_{n}$, there is at most one
accepting computation path of $M_{n}$ on $x$.

  * $\circ$

Similarly, ${\cal M}$ is _weakly-unambiguous_ if, for any index
$n\in\mathbb{N}$, for any input $x\in\Sigma_{n}$, and for any accepting
configuration $conf$, there exists at most one computation path from the
initial configuration of $M_{n}$ on $x$ to $conf$.

  * $\circ$

Moreover, ${\cal M}$ is _reach-unambiguous_ if, for any index
$n\in\mathbb{N}$, for any input $x\in\Sigma_{n}$, and for any configuration
$conf$, there is at most one computation path from the initial configuration
of $M_{n}$ on $x$ to $conf$.

  * $\circ$

In contrast, ${\cal M}$ is _accept-few_ 444This notion is called just “few” in
[15]. For clarity reason, here we use a slightly different term. if there
exist a polynomial $p$ such that, for any index $n\in\mathbb{N}$ and for any
input $x\in\Sigma_{n}$, there are at most $p(n,|x|)$ accepting computation
paths of $M_{n}$ on $x$.

  * $\circ$

Lastly, ${\cal M}$ is _reach-few_ if there exist a polynomial $p$ such that,
for any index $n\in\mathbb{N}$, for any input $x\in\Sigma_{n}$, and for any
configuration $conf$ of $M_{n}$ on $x$, there are at most $p(n,|x|)$
computation paths of $M_{n}$ on $x$ from the initial configuration to $conf$.

The prefix “reach” in “reach-unambiguous” and “reach-few” comes from the
“reachability” of each configuration from the initial configuration.

It is important to remark that all the above five conditions are applied only
to “valid” inputs and there is no requirement for “invalid” inputs.

##  3 Complexity Classes Defined by One-Way Head Moves

We begin with discussing the computational complexity of families of promise
problems solved by nonuniform families of one-way nondeterministic finite
automata of various types introduced in Section 2.3.

We stress that, in our model, along any computation path, a tape head of a
one-way finite automaton always moves to the right (with no
$\varepsilon$-move) until either it reads the right endmarker or it enters a
halting inner state before the right endmarker.

In what follows, we will introduce six nonuniform complexity classes of
families of promise problems and prove the class separations among them, as
depicted in Figure 1.

###  3.1 Definitions of New Complexity Classes

It is important to remark that, since tape heads of 1nfa’s always move to the
right without making any $\varepsilon$-move, we can modify the 1nfa’s so that,
whenever they fail to enter accepting states until reading the right endmarker
$\lhd$, they must enter rejecting states at the time of reading $\lhd$.
Moreover, when the 1nfa’s enter accepting states even before reading $\lhd$,
it is also possible to postpone the timing of acceptance until reading $\lhd$.
The 1nfa’s obtained by these modifications halt precisely at reading $\lhd$.

In a way similar to [2, 5, 15, 19], as various subfamilies of $1\mathrm{N}$,
we introduce six nonuniform state complexity classes associated with
unambiguity and fewness of accepting computation paths given in Section 2.3.

  * $\circ$

$1\mathrm{U}$ consists of all families of promise problems, each family of
which is solved by an appropriate family of 1-way _unambiguous_ finite
automata having polynomially many inner states.

  * $\circ$

$1\mathrm{Few}$ consists of all families of promise problems, each family of
which is solved by an appropriate family of 1-way _accept-few_ finite automata
having polynomially many inner states.

  * $\circ$

$1\mathrm{FewU}$ is defined from $1\mathrm{Few}$, whose underlying finite
automata are additionally _weakly-unambiguous_.

  * $\circ$

$1\mathrm{ReachU}$ is a unique subclass of $1\mathrm{Few}$, whose underlying
finite automata are additionally _reach-unambiguous_.

  * $\circ$

$1\mathrm{ReachFew}$ is a unique subclass of $1\mathrm{Few}$, whose underlying
finite automata are additionally _reach-few_.

  * $\circ$

$1\mathrm{ReachFewU}$ is a unique subclass of $1\mathrm{ReachFew}$, whose
underlying finite automata are additionally _weakly-unambiguous_.

Among the above-mentioned complexity classes, the following inclusion
relationships hold. Figure 1 illustrates these relationships.

###### Lemma 3.1

(1) $1\mathrm{D}\subseteq 1\mathrm{ReachU}\subseteq
1\mathrm{ReachFewU}\subseteq 1\mathrm{ReachFew}\subseteq 1\mathrm{Few}$. (2)
$1\mathrm{D}\subseteq 1\mathrm{U}\subseteq 1\mathrm{FewU}\subseteq
1\mathrm{Few}\subseteq 1\mathrm{N}$.

###### Proof.

We prove only two non-trivial inclusions: $1\mathrm{ReachU}\subseteq
1\mathrm{ReachFewU}$ and $1\mathrm{ReachU}\subseteq 1\mathrm{FewU}$. For any
family ${\cal M}$ of 1nfa’s, if ${\cal M}$ is reach-unambiguous, then it is
also weakly-unambiguous. This implies that $1\mathrm{ReachU}\subseteq
1\mathrm{FewU}$. Moreover, if ${\cal M}$ is reach-unambiguous, then it is also
reach-few. Thus, $1\mathrm{ReachU}\subseteq 1\mathrm{ReachFewU}$ follows
instantly. ∎

Given a class ${\cal C}$ of families of promise problems, we write
$\mathrm{co}\mbox{-}{\cal C}$ for the complexity class $\\{{\cal
L}\mid\mathrm{co}\mbox{-}{\cal L}\in{\cal C}\\}$. The following equality is
easily proven for $1\mathrm{ReachFew}$.

###### Lemma 3.2

$1\mathrm{ReachFew}=\mathrm{co}\mbox{-}1\mathrm{ReachFew}$.

###### Proof.

Let ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be any family
in $1\mathrm{ReachFew}$. Consider a family ${\cal
M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 1nfa’s solving ${\cal L}$
such that each $M_{n}$ is reach-few and accept-few. Since $M_{n}$ is one-way,
it can be assumed to enter either accepting or rejecting states at reading the
right endmarker. We thus define another 1nfa $\overline{M}_{n}$ to be the one
obtained from $M_{n}$ by swapping $Q_{acc,n}$ and $Q_{rej,n}$ of $M_{n}$.
Clearly, $\overline{M}_{n}$ solves $(L_{n}^{(-)},L_{n}^{(+)})$, which belongs
to $\mathrm{co}\mbox{-}{\cal L}$. Note that, at each step of a computation,
the number of distinct configurations of a 1nfa $M_{n}$ is at most a certain
polynomial in $n$. Thus, $\overline{M}_{n}$ is also reach-few and accept-few.
Therefore, $\mathrm{co}\mbox{-}{\cal L}$ belongs to
$\mathrm{co}\mbox{-}1\mathrm{ReachFew}$. ∎

###  3.2 Class Separations Concerning 1ReachU

It is known that $1\mathrm{N}$ is not closed under complementation [17]. This
statement is logically equivalent to $\mathrm{co}\mbox{-}1\mathrm{N}\nsubseteq
1\mathrm{N}$ and this statement was extended in [27] to
$\mathrm{co}\mbox{-}1\mathrm{U}\nsubseteq 1\mathrm{N}$. From this separation
follows the non-closure property of $1\mathrm{U}$ under complementation [27].
Additionally, we wish to demonstrate that
$\mathrm{co}\mbox{-}1\mathrm{ReachU}\nsubseteq 1\mathrm{N}$ by utilizing the
notion of Kolmogorov complexity.

###### Theorem 3.3

$\mathrm{co}\mbox{-}1\mathrm{ReachU}\nsubseteq 1\mathrm{N}$.

To prove the above theorem, let us introduce several important notations.
Given numbers $k,m,n\in\mathbb{N}^{+}$ with $m\geq n$ and
$i_{1},i_{2},\ldots,i_{k}\in[n]$, we use the notation
$\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{k}\;]\\!\\!\\!]\,_{m}$ to be
$1^{i_{1}}0^{m-i_{1}}01^{i_{2}}0^{m-i_{2}}0\cdots 01^{i_{k}}0^{m-i_{k}}$,
where we treat $0^{0}$ as $\lambda$. Here, the value $k$ is called the _size_
of $\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{k}\;]\\!\\!\\!]\,_{m}$. Let $r$
denote any string of the form
$\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{k}\;]\\!\\!\\!]\,_{m}$. We then obtain
$|r|=|\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{k}\;]\\!\\!\\!]\,_{m}|=km+k-1$.
Given any index $e\in[k]$, the notation $(r)_{(e)}$ denotes $i_{e}$ and
$Set(r)$ stands for the set $\\{i_{1},i_{2},\ldots,i_{k}\\}$. When we need to
distinguish multiple occurrences of the same number in $r$, we use another
notation $MSet(r)$ to express its _multi set_. We remark that
$|Set(r)|\leq|MSet(r)|=k$. Let $B_{n}(m,k)$ denote the set of all strings of
the form $\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{k}\;]\\!\\!\\!]\,_{m}$ with
$i_{1},i_{2},\ldots,i_{k}\in[n]$.

Proof of Theorem 3.3.  We introduce the family ${\cal
L}_{1}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of promise decision
problems by setting $L_{n}^{(+)}=\\{u\\#v\mid u,v\in B_{n}(n,n),\exists
e\in[n]((u)_{(e)}\neq(v)_{(e)})\\}$ and $L_{n}^{(-)}=\\{u\\#v\mid u,v\in
B_{n}(n,n),\forall e\in[n]((u)_{(e)}=(v)_{(e)})\\}$ for any index
$n\in\mathbb{N}$. Notice that
$|u|=|\>[\\!\\!\\![\;i_{1},i_{2},\ldots,i_{n}\;]\\!\\!\\!]\,_{n}|=n(n+1)-1$
and $|u\\#u|\leq 2n(n+1)-1$. The complement family of ${\cal L}_{1}$,
$\mathrm{co}\mbox{-}{\cal L}_{1}$, is
$\\{(L_{n}^{(-)},L_{n}^{(+)})\\}_{n\in\mathbb{N}}$. In what follows, we wish
to prove that (1) ${\cal L}_{1}\in 1\mathrm{ReachU}$ and (2)
$\mathrm{co}\mbox{-}{\cal L}_{1}\notin 1\mathrm{N}$. Since
$\mathrm{co}\mbox{-}{\cal L}_{1}\in\mathrm{co}\mbox{-}1\mathrm{ReachU}$,
“$\mathrm{co}\mbox{-}{\cal L}_{1}\notin 1\mathrm{N}$” derives the theorem.

(1) Let us first prove that ${\cal L}_{1}$ belongs to $1\mathrm{FewU}$. This
can be shown by constructing a family of polynomial-size, accept-few, weakly-
unambiguous 1nfa’s $N_{n}$ that solves ${\cal L}_{1}$. We make each $N_{n}$
have $n$ accepting inner states, say,
$Q_{acc,n}=\\{\hat{q}_{1},\hat{q}_{2},\ldots,\hat{q}_{n}\\}$. On input $x$ of
the form $r_{1}\\#r_{2}$ with $r_{1},r_{2}\in B_{n}(n,n)$, guess (i.e.,
nondeterministically choose) an index $e\in[n]$, read $r_{1}$, remember the
$e$th entry $i_{e}=(r_{1})_{(e)}$ by entering inner states of the form
$(i_{e},e)$, read $r_{2}$, and check whether $i_{e}$ coincides with
$(r_{2})_{(e)}$. If so, enter the $e$th accepting state $\hat{q}_{e}$. It is
easy to show that $N_{n}$ solves $(L_{n}^{(+)},L_{n}^{(-)})$ correctly. Notice
that, for each accepting inner state $\hat{q}_{e}$, there are at most one
accepting computation path leading to $\hat{q}_{e}$. Thus, $N_{n}$ is accept-
few and also weakly-unambiguous. Since $\\{N_{n}\\}_{n\in\mathbb{N}}$ solves
${\cal L}_{1}$, it belongs to $1\mathrm{ReachU}$.

(2) To verify that $\mathrm{co}\mbox{-}{\cal L}_{1}\notin 1\mathrm{N}$, let us
assume that $\mathrm{co}\mbox{-}{\cal L}_{1}\in 1\mathrm{N}$ and take a family
${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 1nfa’s that solves
$\mathrm{co}\mbox{-}{\cal L}_{1}$. For each index $n\in\mathbb{N}$, we write
$Q_{n}$ for the set of all inner states of $M_{n}$. The cardinality of such
the set $Q_{n}$ is upper-bounded by an appropriately fixed polynomial, say,
$p$; namely, $|Q_{n}|\leq p(n)$ for all $n\in\mathbb{N}$. For our convenience,
we express all elements of $Q_{n}$ as numbers in $[0,|Q_{n}|-1]_{\mathbb{Z}}$.
Take a sufficiently large $n$ satisfying $p(n)<2^{n}$. Given any
$n\in\mathbb{N}$ and any string $u\in B_{n}(n,n)$, we define $S_{n}(u)$ to be
the set of all inner states $q$ in $Q_{n}$ such that, in a certain accepting
computation path of $M_{n}$ on input $u\\#u$, $M_{n}$ enters $q$ just after
reading $u\\#$.

Recall from Section 2.1 the notion of the (unconditional) Kolmogorov
complexity $C(w)$ of a string $w$. There exists a string $u$ in $B_{n}(n,n)$
such that $C(u)\geq n\log{n}-1$. If there is no such $u$, we then define a
mapping from $B_{n}(n,n)$ to $\Sigma^{*}$ as follows. Given each element $u$
in $B_{n}(n,n)$, we assign to $u$ a “minimal” program $p_{u}$ that the
universal Turing machine $U$ takes $p_{u}$ as an input and produces $u$ on its
output tape. Since $C(u)=|p_{r}|$, we obtain $|p_{r}|<n\log{n}-1$. This
implies $\|B_{n}(n,n)\|\leq\|\\{0,1\\}^{<n\log{n}-1}\|=2^{n\log{n}-1}$. This
is a contradiction.

Now, we evaluate the value $C(u)$. Note that the length of the binary
expression of $q$ is $O(\log{n})$ since $|Q_{n}|\leq p(n)$. Take an inner
state $q\in S_{n}(u)$ making $C(q)$ be the smallest. Let us design a
deterministic algorithm, say, ${\cal B}$ that begins with the empty input
$\varepsilon$ and produces $u$ on an output tapes. The algorithm ${\cal B}$
recursively picks up strings $w\in B_{n}(n,n)$ one by one, runs $M_{n}$ on
$w\\#w$ starting with the inner state $q$. If $M_{n}$ enters no accepting
states on all computation paths, then ${\cal B}$ outputs $w$ and halts.
Otherwise, ${\cal B}$ picks up another $w$ and continues the above procedure.
Let $r_{0}$ denote the binary encoding of this algorithm ${\cal B}$. Notice
$C(q)\leq|bin(q)|$. Since ${\cal B}$ requires the knowledge of $(n,q)$ to run,
it follows that $C(u)\leq|bin(n)|+|bin(q)|+|r_{0}|+O(1)\leq O(\log{n})$, which
is in contradiction to $C(u)\geq n\log{n}-1$. $\Box$

An instant corollary of Theorem 3.3 is the non-closure property under
complementation for two complexity classes: $1\mathrm{ReachU}$,
$1\mathrm{ReachFewU}$, $1\mathrm{FewU}$, and $1\mathrm{Few}$.

###### Corollary 3.4

$1\mathrm{ReachU}\neq\mathrm{co}\mbox{-}1\mathrm{ReachU}$,
$1\mathrm{ReachFewU}\neq\mathrm{co}\mbox{-}1\mathrm{ReachFewU}$,
$1\mathrm{FewU}\neq\mathrm{co}\mbox{-}1\mathrm{FewU}$, and
$1\mathrm{Few}\neq\mathrm{co}\mbox{-}1\mathrm{Few}$.

###### Proof.

Assume that $1\mathrm{ReachU}=\mathrm{co}\mbox{-}1\mathrm{ReachU}$. Since
$1\mathrm{ReachU}\subseteq 1\mathrm{N}$, we obtain
$\mathrm{co}\mbox{-}1\mathrm{ReachU}\subseteq 1\mathrm{N}$. This contradicts
Theorem 3.3. Thus, we conclude that
$1\mathrm{ReachU}\neq\mathrm{co}\mbox{-}1\mathrm{ReachU}$. The same argument
works for $1\mathrm{ReachFewU}$, $1\mathrm{FewU}$, and $1\mathrm{Few}$ since
these classes include $1\mathrm{ReachU}$. ∎

Another implication of Theorem 3.3 is the class separations between
$1\mathrm{ReachFew}$ and $1\mathrm{Few}$ as well as between $1\mathrm{D}$ and
$1\mathrm{ReachU}$.

###### Corollary 3.5

(1) $1\mathrm{D}\neq 1\mathrm{ReachU}$. (2) $1\mathrm{ReachFewU}\neq
1\mathrm{ReachFew}$. (3) $1\mathrm{ReachFew}\neq 1\mathrm{Few}$.

###### Proof.

(1) Obviously, $1\mathrm{ReachU}$ contains $1\mathrm{D}$. If
$1\mathrm{D}=1\mathrm{ReachU}$, then we obtain
$1\mathrm{D}=\mathrm{co}\mbox{-}1\mathrm{ReachU}$ because of
$1\mathrm{D}=\mathrm{co}\mbox{-}1\mathrm{D}$. This implies that
$\mathrm{co}\mbox{-}1\mathrm{ReachU}\subseteq 1\mathrm{N}$, a contradiction
with Theorem 3.3.

(2) Since $1\mathrm{ReachFew}=\mathrm{co}\mbox{-}1\mathrm{ReachFew}$ by Lemma
3.2, Theorem 3.3 then implies that $1\mathrm{ReachFewU}\neq
1\mathrm{ReachFew}$.

(3) If $1\mathrm{ReachFew}=1\mathrm{Few}$, then Corollary 3.4(1) implies that
$1\mathrm{ReachFew}=1\mathrm{Few}\neq\mathrm{co}\mbox{-}1\mathrm{Few}=\mathrm{co}\mbox{-}1\mathrm{ReachFew}$.
However, this is in contradiction to Lemma 3.2. ∎

Corollary 3.5(2) immediately draws a conclusion that $1\mathrm{ReachFew}\neq
1\mathrm{ReachU}$. This is not true for the corresponding log-space complexity
classes: $\mathrm{ReachFewL}$ and $\mathrm{ReachUL}$ [6].

###  3.3 Class Separations Concerning 1U

We next look into the computational complexity of $1\mathrm{U}$, which is a
one-way finite automata analogue of the complexity class $\mathrm{UP}$. From
Lemma 3.1 follows $1\mathrm{ReachFewU}\subseteq 1\mathrm{FewU}$. In what
follows, we assert that $1\mathrm{FewU}$ is an optimal upper bound of
$1\mathrm{ReachFewU}$ by demonstrating the difference between $1\mathrm{U}$
and $1\mathrm{FewU}$.

###### Theorem 3.6

$1\mathrm{ReachU}\nsubseteq 1\mathrm{U}$.

It was noted in [27] that there is a close connection between one-tape linear-
time advised Turing machines and nonuniform finite automata families, in
particular, a connection between $1\mbox{-}\mathrm{C}_{=}\mathrm{LIN}/lin$ and
$1\mathrm{C_{=}}$. This connection was adapted to prove the separation of
$1\mathrm{C_{=}}$ from $1\mathrm{N}$. A key to this separation is a lemma
(Lemma 12) of [27] expressing a specific feature of families of promise
problems in $1\mathrm{C_{=}}$. To prove Theorem 3.6, we wish to generalize
this key lemma to Lemma 3.7 and apply it in the proof of the theorem.

For the generalization of the key lemma in [27], we first need to convert the
current model of 1nfa into the following model of _one-way probabilistic
finite automata_ (or 1pfa’s, for short). A 1pfa $N$ has the form
$(Q,\Sigma,\\{\triangleright,\triangleleft\\},\nu_{ini},\\{M_{\sigma}\\}_{\sigma\in\check{\Sigma}},Q_{acc},Q_{rej})$
with a $|Q|$-dimensional (row) vector $\nu_{ini}$ and a set of $|Q|\times|Q|$
stochastic555A square matrix of nonnegative real entries is called
_stochastic_ if every row of the matrix sums up to exactly $1$. matrices
$M_{\sigma}$ for each symbol $\sigma$. Given a string $x=x_{1}x_{2}\cdots
x_{n}$ in $\check{\Sigma}^{*}$, we abbreviate as $M_{x}$ the matrix product
$M_{x_{1}}M_{x_{2}}\cdots M_{x_{n}}$. We fix an accepting inner state
$q_{acc}\in Q_{acc}$. We further define a $|Q|$-dimensional (row) vector
$\xi_{acc}(q_{acc})=(\xi_{q})_{q\in Q}$ associated with $q_{acc}$ by setting
$\xi_{q_{acc}}=1$ and $\xi_{q}=0$ for all $q\in Q-\\{q_{acc}\\}$. The
acceptance probability of $N$ on input $x$ leading to $q_{acc}$ is denoted
$p_{acc}(x:q_{acc})$, which is defined as $\nu_{ini}M_{\triangleright
x\triangleleft}\xi_{acc}(q_{acc})^{T}$, where $T$ refers to the “transpose” of
a vector. Moreover, we set $p_{acc}(x)$ to be $\sum_{q\in
Q_{acc}}p_{acc}(x:q)$, which is the acceptance probability of $N$ on input
$x$.

Given a 1nfa $M=(Q,\Sigma,\delta,q_{0},Q_{acc},Q_{rej})$ in the branching
normal form, consider the following conversion of it into the corresponding
1pfa $N$. Take a constant $c\geq 1$ fir which $M$ makes exactly $c$
nondeterministic choices at every step. We further expand $\delta$ to the
domain $Q\times\check{\Sigma}$ (from $(Q-Q_{halt})\times\check{\Sigma}$) by
assigning $\delta(q,\sigma)=\\{q\\}$ for all $q\in Q_{halt}$ and all
$\sigma\in\check{\Sigma}$. We turn a nondeterministic choice of $M$ to a
probabilistic choice of $N$ made with probability $1/c$ by defining
$M_{\sigma}=(a_{ij})_{i,j\in Q}$ as $a_{ij}=1/c$ if $j\in\delta(i,\sigma)$ and
$a_{ij}=0$ otherwise. Since $|\delta(i,\sigma)|=c$ for any $(i,\sigma)$, the
$i$th row of $M_{\sigma}$ has exactly $c$ nonzero entries, and thus all
entries in the $i$th row sum up to $1$. This guarantees the stochasticity of
$M_{\sigma}$. Moreover, the total number of accepting computation paths of $M$
on $x$ matches the total acceptance probability of $N$ on $x$.

###### Lemma 3.7

Let ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ be a family of polynomial-size
1pfa’s over alphabet $\Sigma$ in which each $M_{n}$ makes exactly $c$
probabilistic choices with equal probability at every step for a fixed
constant $c\in\mathbb{N}^{+}$ (independent of $n$). For each index
$n\in\mathbb{N}$, let $D_{n}$ denote a set of valid instances in $\Sigma^{*}$.
Let $f:\mathbb{N}^{3}\times Q_{acc,n}\to[0,1]$ be a function, where
$Q_{acc,n}$ is the set of all accepting inner states of $M_{n}$. In this case,
there exists a polynomial $p$ that satisfies the following statement. (*) For
any numbers $n,m,l\in\mathbb{N}^{+}$ with $l\leq m-1$ and any accepting inner
state $q\in Q_{acc,n}$, there exists a subset $S$ of
$A_{n,m,l,q}=\\{x\in\Sigma^{m-l}\mid\exists z\in\Sigma^{l}\>[xz\in D_{n}\wedge
p_{acc,n}(xz:q)=f(n,|xz|,|z|,q)]\\}$ with $|S|\leq p(n)$ such that, for any
$y\in\Sigma^{l}$, if $wy\in D_{n}$ and $p_{acc,n}(wy:c)=f(n,m,l,q)$ for all
$w\in S$, then $p_{acc,n}(xy:q)=f(n,m,l,q)$ holds for all $x\in A_{n,m,l,q}$
with $xy\in D_{n}$.

###### Proof.

Let ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ be any given family of polynomial-
size 1pfa’s over alphabet $\Sigma$, where each $M_{n}$ has the form
$(Q_{n},\Sigma,\\{\triangleright,\triangleleft\\},\nu_{ini}^{(n)},\\{M^{(n)}_{\sigma}\\}_{\sigma\in\check{\Sigma}},Q_{acc,n},Q_{rej,n})$,
making exactly $c$ probabilistic choices with equal probability at every step.
Notice that, for any $m,n\in\mathbb{N}$, any input $x\in\Sigma^{m}\cap D_{n}$,
and any accepting inner state $q$ of $M_{n}$, $p_{acc,n}(x:q)$ equals
$\nu_{ini}^{(x)}M^{(n)}_{\triangleright x\triangleleft}\xi_{acc,n}(q)^{T}$. We
remark that, when $M_{n}$ reads the right endmarker $\triangleleft$ on any
valid input $x$, each computation path of $M_{n}$ on $x$ is generated with
probability exactly $c^{|x|+2}$. Since ${\cal M}$ has polynomial size, there
is a polynomial $p$ satisfying $|Q_{n}|\leq p(n)$ for all $n\in\mathbb{N}$.

We fix $n$ arbitrarily and take $m,l\in\mathbb{N}^{+}$ with $l\leq m-1$ and
$q\in Q_{acc,n}$. The notation $A_{n,m,l,q}$ denotes the set
$\\{x\in\Sigma^{m-l}\mid\exists z\in\Sigma^{l}\>[xz\in D_{n}\wedge
p_{acc,n}(xz:q)=f(n,|xz|,|z|,q)]\\}$. We consider the set
$V_{n,m,l,q}=\\{\nu_{ini}^{(n)}M^{(n)}_{\triangleright x}\mid x\in
A_{n,m,l,q}\\}$ of $|Q_{n}|$-dimensional vectors. Note that
$|V_{n,m,l,q}|\leq|\Sigma|^{m-l}$. We choose a maximal subset of linearly-
independent vectors in $V_{n,m,l,q}$. Since all vectors in $V_{n,m,l,q}$ are
$|Q_{n}|$-dimensional, such a subset is expressed as
$\\{\nu_{ini}^{(n)}M_{\triangleright w}\mid w\in S\\}$ for a certain subset
$S$ of $\Sigma^{m-l}$ of size at most $|Q_{n}|$. It then follows that, for any
$x$ with $|x|=m-l$, by the choice of $\\{\nu_{ini}^{(n)}M_{\triangleright
w}\mid w\in S\\}$, there exists a series $\\{\alpha^{(x)}_{w}\\}_{w\in S}$ of
real numbers satisfying that $\nu_{ini}^{(n)}M^{(n)}_{\triangleright
x}=\sum_{w\in S}\alpha^{(n)}_{w}\nu_{ini}^{(n)}M^{(n)}_{\triangleright w}$.
Here, we claim that $\sum_{w\in S}\alpha^{(x)}_{w}=1$. To prove this claim,
let $\nu_{ini}^{(n)}M^{(n)}_{\triangleright w}=(a_{wi})_{i\in[m]}$ and
$\nu^{(n)}_{ini}M^{(n)}_{\triangleright x}=(b_{xi})_{i\in[m]}$. It then
follows that $(b_{xi})_{i\in[m]}=(\sum_{w\in
S}\alpha^{(x)}_{w}a_{wi})_{i\in[m]}$. From this follows
$\sum_{i\in[m]}b_{xi}=\sum_{w\in
S}(\sum_{i\in[m]}\alpha^{(x)}_{w}a_{wi})=\sum_{w\in
S}\alpha^{(x)}_{w}(\sum_{i\in[m]}a_{wi})$. The stochasticity of
$M^{(n)}_{\triangleright x}$ and $M^{(n)}_{\triangleright w}$ implies that
$\sum_{i\in[m]}b_{xi}=\sum_{i\in[m]}a_{wi}=1$. Therefore, we conclude that
$\sum_{w\in S}\alpha^{(x)}_{w}=1$.

We fix $y\in\Sigma^{l}$ and $q\in Q_{acc,n}$ arbitrarily and assume that
$wy\in D_{n}$ and $p_{acc,n}(wy:q)=f(n,m,l,q)$ for all $w\in S$. Take any
string $x\in A_{n,m,l,q}$ satisfying $xy\in D_{n}$. It then follows that
$p_{acc,n}(xy:q)=\nu_{ini}^{(n)}M^{(n)}_{\triangleright
xy\triangleleft}\xi_{acc,n}(q)^{T}=(\nu_{ini}^{(n)}M_{\triangleright
x})(M_{y\triangleleft}\xi_{acc,n}(q)^{T})=(\sum_{w\in
S}\alpha^{(x)}_{w}\nu_{ini}^{(n)}M^{(n)}_{\triangleright
w})(M^{(n)}_{y\triangleleft}\xi_{acc,n}(q)^{T})=\sum_{w\in
S}\alpha^{(x)}_{w}(\nu_{ini}^{(n)}M^{(n)}_{\triangleright
wy\triangleleft}\xi_{acc,n}(q)^{T})=\sum_{w\in
S}\alpha^{(x)}_{w}p_{acc,n}(wy:q)$. The last term is equal to $\sum_{w\in
S}\alpha^{(x)}_{w}f(n,m,l,q)=(\sum_{w\in S}\alpha^{(x)}_{w})f(n,m,l,q)$. Since
$\sum_{w\in S}\alpha^{(x)}_{w}=1$, we obtain $p_{acc,n}(xy:q)=f(n,m,l,q)$, as
requested. ∎

In Lemma 3.7, the use of the equality “$=$” in the above formula
$p_{acc,n}(xz:q)=f(n,|xz|,|z|,q)$ is crucial because, if “$=$” is replaced by,
e.g., “$\leq$”, then we may not be able to prove a statement similar to (*) in
the lemma.

Now, we provide the proof of Theorem 3.6 using Lemma 3.7.

Proof of Theorem 3.6.  As an example family that falls in $1\mathrm{ReachU}$,
let us recall the family ${\cal
L}_{1}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ introduced in the
proof of Theorem 3.3. We thus need to verify that ${\cal L}_{1}\notin
1\mathrm{U}$. Toward a contradiction, we assume the existence of a family
${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size unambiguous 1nfa’s
that solves ${\cal L}_{1}$. By Lemma 2.2, we can assume that $M_{n}$ makes
exactly $c$ nondeterministic choices at every step. Moreover, we can keep
$M_{n}$ unambiguous on all valid instances. Since $M_{n}$ is unambiguous, it
is possible to assume that $|Q_{acc,n}|=1$ for all $n\in\mathbb{N}$. Let
$Q_{acc,n}=\\{q_{acc}\\}$. For clarity reason, we denote $L_{n}^{(+)}\cup
L_{n}^{(-)}$ by $D_{n}$. By the definition of $(L_{n}^{(+)},L_{n}^{(-)})$, it
follows that $x\in D_{n}$ implies $|x|=2n(n+1)-1$ since $x$ is of the form
$r_{1}\\#r_{2}$ for certain strings $r_{1},r_{2}\in B_{n}(n,n)$. Since ${\cal
M}$ has polynomial size, there is a certain polynomial $p^{\prime}$ satisfying
$|Q_{n}|\leq p^{\prime}(n)$ for all $n\in\mathbb{N}$.

As noted earlier, we can convert $M_{n}$ into a 1pfa of the form
$(Q_{n},\Sigma,\\{\triangleright,\triangleleft\\},\nu_{ini}^{(n)},\\{M^{(n)}_{\sigma}\\}_{\sigma\in\check{\Sigma}},Q_{acc,n},Q_{rej,n})$
with the following acceptance criteria: for any $x$, $x\in L_{n}^{(+)}$
implies $p_{acc,n}(x)=1/c^{|x|+2}$ and $x\in L_{n}^{(-)}$ implies
$p_{acc,n}(x)=0$. It is important to remark that this 1pfa $M_{n}$ has only
one accepting inner state $q_{acc}$, and thus $p_{acc,n}(x:q_{acc})$ matches
$p_{acc,n}(x)$.

For any $n,m,l\in\mathbb{N}$, we further define $f(n,m,l,q_{acc})$ to be
$1/c^{m+2}$. By Lemma 3.7, there is a polynomial $p$ that satisfies the lemma.
In what follows, we fix a number $n\in\mathbb{N}$ that guarantees that
$p(n)+p^{\prime}(n)+1<n^{n}$. Let $m=2n(n+1)-1$ and $l=n(n+1)-1$. Moreover, we
fix $r_{0}=\>[\\!\\!\\![\;1,1,\ldots,1\;]\\!\\!\\!]\,_{n}$ in $B_{n}(n,n)$.
Note that $|r_{0}|=l$ and $|r\\#r_{0}|=m$ for all elements $r\in B_{n}(n,n)$.
The notation $A_{n,m,l,q_{acc}}$ denotes the set $\\{r\\#\mid r\in
B_{n}(n,n),\exists r^{\prime}\in
B_{n}(n,n)\>[p_{acc,n}(r\\#r^{\prime})=f(n,|r\\#r^{\prime}|,|r^{\prime}|,q_{acc})]\\}$.
The lemma ensures the existence of a set $S\subseteq A_{n,m,l,q_{acc}}$ with
$|S|\leq p(n)$ that satisfies the statement (*) of the lemma. We choose a
string $y\in B_{n}(n,n)$ satisfying $y\\#\notin S\cup\\{r_{0}\\#\\}$. This is
possible because $|S|\leq p(n)$ and $|B_{n}(n,n)|=n^{n}$. Notice that $y\\#$
is in $A_{n,m,l,q_{acc}}$ since $p_{acc,n}(y\\#r_{0})=1/c^{|y\\#r_{0}|+2}$.
For any $r\\#\in S$, since $r\neq y$, we obtain $r\\#y\in L_{n}^{(+)}$, and
thus $p_{acc,n}(r\\#y)=f(n,m,l,q_{acc})$ follows. The statement (*) of the
lemma then concludes that $p_{acc,n}(r\\#y)=f(n,m,l,q_{acc})$ for all $r\\#\in
A_{n,m,l,q_{acc}}$. As a special case, we choose $y$ as $r$, and thus
$p_{acc,n}(y\\#y)=f(n,m,l,q_{acc})$ follows. Therefore, $y\\#y$ belongs to
$L_{n}^{(+)}$, a contradiction with the fact that $y\\#y\in L_{n}^{(-)}$.

This completes the proof. $\Box$

Pavan et al. [15] demonstrated that $\mathrm{ReachFewL}$ is included in
$\mathrm{UL}\cap\mathrm{co}\mbox{-}\mathrm{UL}$. A simple analogy could
suggest that $1\mathrm{ReachFew}$ might be included in
$1\mathrm{U}\cap\mathrm{co}\mbox{-}1\mathrm{U}$. However, this analogy does
not hold because we instantly obtain $1\mathrm{ReachFew}\nsubseteq
1\mathrm{U}$ from Theorem 3.6.

###  3.4 Class Separations Concerning 1FewU

Let us recall the key lemma, Lemma 3.7, of Section 3.3 and we intend to apply
it to show another separation between $1\mathrm{FewU}$ and $1\mathrm{N}$.

###### Theorem 3.8

$1\mathrm{N}\nsubseteq 1\mathrm{FewU}$.

Given $n\in\mathbb{N}^{+}$, let us consider an $n\times n$ matrix
$D=(a_{ij})_{i,j\in[n]}$ whose $(i,j)$-entry $a_{ij}$ is in $[n]$. For each
index $i\in[n]$, the notation $D(i)$ denotes the $i$th row
$(a_{i1},a_{i2},\ldots,a_{in})$ of $D$. Associated with this row $D(i)$, we
encode it into a unique string $\>[\\!\\!\\![\;D(i)\;]\\!\\!\\!]\,_{n}$ of the
form $\>[\\!\\!\\![\;a_{i1},a_{i2},\ldots,a_{in}\;]\\!\\!\\!]\,_{n}$.
Moreover, the encoding of $D$ is given as
$\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}=\>[\\!\\!\\![\;D(1)\;]\\!\\!\\!]\,_{n}\\#\>[\\!\\!\\![\;D(2)\;]\\!\\!\\!]\,_{n}\\#\cdots\\#\>[\\!\\!\\![\;D(n)\;]\\!\\!\\!]\,_{n}$.
Note that $|\>[\\!\\!\\![\;D(i)\;]\\!\\!\\!]\,_{n}|=n(n+1)-1$ for any
$i\in[n]$ and $|\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}|=n^{2}(n+1)-1$. For
convenience, $T_{n}$ denotes the set $\\{D\mid D=(a_{ij})_{i,j\in[n]}\text{ is
an $n\times n$ matrix with $a_{ij}\in[n]$ for any $i,j\in[n]$ }\\}$.

Proof of Theorem 3.8.  Let $n\in\mathbb{N}^{+}$, take a matrix
$D=(a_{ij})_{i,j\in[n]}$ in $T_{n}$, and consider its encoding
$\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}$. Using a choice function
$\sigma:[n]\to[n]$, we define $sum_{D}(\sigma)=\sum_{i=1}^{n}a_{i\sigma(i)}$.

For each index $n\in\mathbb{N}$, we define
$L_{n}^{(+)}=\\{\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\mid
D,D^{\prime}\in
T_{n},\exists\sigma,\sigma^{\prime}\>[sum_{D}(\sigma)=sum_{D^{\prime}}(\sigma^{\prime})]\\}$
and
$L_{n}^{(-)}=\\{\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\mid
D,D^{\prime}\in T_{n},\forall\sigma,\sigma^{\prime}\>[sum_{D}(\sigma)\neq
sum_{D^{\prime}}(\sigma^{\prime})]\\}$. We then set ${\cal L}_{2}$ to be the
family $\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$. Hereafter, we
intend to prove (1) ${\cal L}_{2}\in 1\mathrm{N}$ and (2) ${\cal L}_{2}\notin
1\mathrm{FewU}$ to complete the proof.

(1) We first show that ${\cal L}_{2}\in 1\mathrm{N}$. We arbitrarily fix
$n\in\mathbb{N}$ and consider the following 1nfa $N_{n}$. Let an input have
the form
$\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}$
with $D,D^{\prime}\in T_{n}$, where $D=(a_{ij})_{i,j\in[n]}$ and
$D^{\prime}=(a^{\prime}_{ij})_{i,j\in[n]}$. While reading
$\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}$, for each $i\in[n]$,
nondeterministically choose one entry, say, $a_{ij_{i}}$ ($j_{i}\in[n]$) from
the $i$th row $D(i)$ and compute $\bar{a}=\sum_{i\in[m]}a_{ij_{i}}$. Remember
$\bar{a}$ and cross $\\#^{2}$ to
$\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}$. Repeat the same procedure to
compute $\bar{a}^{\prime}=\sum_{i\in[n]}a^{\prime}_{ik_{i}}$. Check whether
$\bar{a}=\bar{a}^{\prime}$. If so, enter an accepting inner state; otherwise,
enter a rejecting inner state. This machine $N_{n}$ is obviously a 1nfa and
correctly solves $(L_{n}^{(+)},L_{n}^{(-)})$. Therefore, ${\cal L}_{2}$
belongs to $1\mathrm{N}$.

(2) Next, we want to show that ${\cal L}_{2}\notin 1\mathrm{FewU}$ by way of
contradiction. Assume that ${\cal L}_{2}\in 1\mathrm{FewU}$ and take a family
${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size, accept-few,
weakly-unambiguous 1nfa’s that correctly solves ${\cal L}_{2}$. It is possible
to assume by Lemma 2.2 that $M_{n}$ makes exactly $c$ nondeterministic choices
at every step for a certain fixed constant $c\geq 1$. As done in Section 3.3,
we can convert $M_{n}$ into a 1pfa with the following acceptance criteria: for
any $x\in L_{n}^{(+)}\cup L_{n}^{(-)}$, $x\in L_{n}^{(+)}$ implies that there
is an inner state $q\in Q_{acc,n}$ for which $p_{acc,n}(x:q)=1/c^{|x|+2}$ and
$x\in L_{n}^{(-)}$ implies that, for all $q\in Q_{acc,n}$, $p_{acc,n}(x:q)=0$.
We then define $f(n,m,l,q)=1/c^{m+2}$. Given any $D^{\prime}\in T_{n}$,
$C_{n}(D^{\prime})$ denotes the set $\\{D\in
T_{n}\mid\forall\sigma,\sigma^{\prime}\>[sum_{D}(\sigma)\neq
sum_{D^{\prime}}(\sigma^{\prime})]\\}$.

To lead to a desired contradiction, we apply Lemma 3.7 and take a polynomial
$p$ that satisfies the lemma. Let $D_{0}$ denote the $n\times n$ matrix whose
entries are all $1$. Clearly, $D_{0}$ is in $T_{n}$. Let $m=n^{2}(n+1)-1$ and
$l=n(n+1)-1$. Given any $q\in Q_{acc,n}$, we introduce the set
$A_{n,m,l,q}=\\{\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\mid D\in
T_{n},\exists D^{\prime}\in
T_{n}\>[p_{acc,n}(\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}:q)=f(n,m,l,q)]\\}$.
For convenience, we introduce the notation $A_{n,m,l,q}^{(-)}$ defined to be
$\\{D\in T_{n}\mid\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\in
A_{n,m,l,q}\\}$. We then take a subset $S$ of $A_{n,m,l,q}$ of size at most
$p(n)$ that satisfies the statement (*) of the lemma. We choose an arbitrary
matrix $D\in A^{(-)}_{n,m,l,q}$ outside of $\\{D^{\prime\prime}\in
C_{n}(D^{\prime})\mid D^{\prime}=D_{0}\text{ or
}\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\\#^{2}\in S\\}$. This $D$
satisfies the following property: for any $D^{\prime}\in T_{n}$, if
$\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\\#^{2}$ is in $S$, then
$p_{acc,n}(\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}:q)=f(n,m,l,q)$
since $D\notin C_{n}(D^{\prime})$. Therefore, by the conclusion of the
statement (*),
$p_{acc,n}(\>[\\!\\!\\![\;D^{\prime}\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}:q)=f(n,m,l,q)$
follows for all $D^{\prime}\in A^{(-)}_{n,m,l,q}$. In particular, we set
$D^{\prime}=D$ and obtain
$p_{acc,n}(\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}:q)=f(n,m,l,q)$.
This implies that
$\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\\#^{2}\>[\\!\\!\\![\;D\;]\\!\\!\\!]\,_{n}\in
L_{n}^{(+)}$. Obviously, this is in contradiction to the definition of
$L_{n}^{(+)}$. $\Box$

We can conclude the following, rather weak, statement from Theorem 3.8.

###### Corollary 3.9

Either $1\mathrm{Few}\neq 1\mathrm{N}$ or $1\mathrm{FewU}\neq 1\mathrm{Few}$
(or both) is true.

##  4 Complexity Classes Defined by Two-Way Head Moves

In Section 3.1, we have introduced six nonuniform state complexity classes
situated in between $1\mathrm{D}$ and $1\mathrm{N}$. By replacing underlying
one-way finite automata defining those complexity classes with two-way finite
automata, we naturally obtain the corresponding six nonuniform state
complexity classes: $2\mathrm{U}$, $2\mathrm{ReachU}$, $2\mathrm{ReachFewU}$,
$2\mathrm{ReachFew}$, $2\mathrm{FewU}$, and $2\mathrm{Few}$. Similar to Lemma
3.1 for the case of one-way head moves, these classes satisfy the following
clear inclusion relationships: (1) $2\mathrm{D}\subseteq
2\mathrm{ReachU}\subseteq 2\mathrm{ReachFewU}\subseteq
2\mathrm{ReachFew}\subseteq 2\mathrm{Few}$ and (2) $2\mathrm{D}\subseteq
2\mathrm{U}\subseteq 2\mathrm{FewU}\subseteq 2\mathrm{Few}\subseteq
2\mathrm{N}$.

###  4.1 Cases of Logarithmic and Polynomial Ceilings

A family ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of
promise problems is said to _have a polynomial ceiling_ if there exists a
polynomial $p$ for which $\Sigma_{n}\subseteq\Sigma^{\leq p(n)}$ holds for all
$n\in\mathbb{N}$, where $\Sigma_{n}$ denotes the set $L_{n}^{(+)}\cup
L_{n}^{(-)}$. Similarly, we can define the notion of _exponential ceiling_
(resp., _logarithmic ceiling_) simply by replacing the term “polynomial” with
“exponential” (resp., “logarithmic function”). More generally, given a
function $g:\mathbb{N}\to\mathbb{N}$, we say that ${\cal L}$ has a _$g(n)$
-ceiling_ if $\Sigma_{n}\subseteq\Sigma^{\leq g(n)}$ holds for any number
$n\in\mathbb{N}$.

For two functions $f$ and $g$ on $\mathbb{N}$ (i.e., from $\mathbb{N}$ to
$\mathbb{N}$), we say that $g$ _majorizes_ $f$ (denoted $g\geq f$) if
$g(n)\geq f(n)$ holds for all $n\in\mathbb{N}$. Consider a family ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ of promise problems
having an $f(n)$-ceiling. It then follows that $L_{n}^{(+)}=\\{x\in
L_{n}^{(+)}\mid|x|\leq f(n)\\}$ and $L_{n}^{(-)}=\\{x\in
L_{n}^{(-)}\mid|x|\leq f(n)\\}$. For any function $g$ on $\mathbb{N}$, if $g$
majorizes $f$, then we obtain $\Sigma_{n}\subseteq\Sigma^{\leq
f(n)}\subseteq\Sigma^{\leq g(n)}$, and thus ${\cal L}$ has a $g(n)$-ceiling as
well. Hence, for instance, any polynomial ceiling family of promise problems
has an exponential ceiling as well.

Given a function $f$ on $\mathbb{N}$, the notation $2\mathrm{N}/f(n)$ stands
for the subclass of $2\mathrm{N}$, consisting of all families of promise
problems having $f(n)$-ceilings. Notice that $g\geq f$ implies
$2\mathrm{N}/f(n)\subseteq 2\mathrm{N}/g(n)$. For a set ${\cal F}$ of
functions on $\mathbb{N}$, $2\mathrm{N}/{\cal F}$ denotes the union of all
$2\mathrm{N}/f(n)$ for any $f\in{\cal F}$. In a similar way, we obtain
$2\mathrm{D}/{\cal F}$ from $2\mathrm{D}$. These terminologies are also
applied to $2\mathrm{FewU}$, $2\mathrm{ReachU}$, $2\mathrm{ReachFew}$, and
$2\mathrm{ReachFewU}$.

For convenience, we abbreviate the sets of logarithmic functions, polynomials,
exponentials, and sub-exponentials, as “$\log$”, “$\mathrm{poly}$”,
“$\mathrm{exp}$”, and “$\mathrm{subexp}$”, respectively. This subsection will
concentrate on the case where ${\cal F}$ is one of those sets of functions. We
start with an easy case of ${\cal F}=\log$.

###### Proposition 4.1

$2\mathrm{N}/\mathrm{log}=2\mathrm{D}/\mathrm{log}$. More strongly,
$2\mathrm{N}/\mathrm{log}\subseteq 1\mathrm{D}$.

###### Proof.

Let us prove that $2\mathrm{N}/\mathrm{log}\subseteq 1\mathrm{D}$ because this
inclusion implies $2\mathrm{N}/\mathrm{log}\subseteq
1\mathrm{D}/\mathrm{log}\subseteq 2\mathrm{D}/\mathrm{log}$. Toward
$2\mathrm{N}/\mathrm{log}\subseteq 1\mathrm{D}$, let ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be any family of promise
problems in $2\mathrm{N}/\mathrm{log}$. Take a function $\ell(x)$ of the form
$a\log x+b$ for two constants $a,b\geq 0$. Notice that
$\Sigma_{n}\subseteq\Sigma^{\leq\ell(n)}$, where $\Sigma_{n}=L_{n}^{(+)}\cup
L_{n}^{(-)}$. and $|\Sigma^{\ell(n)}|=O(n^{a})$. It then follows that
$|\Sigma^{\leq\ell(n)}|=n^{O(1)}$.

Fix $n\in\mathbb{N}$ arbitrarily. We enumerate all elements in
$\Sigma^{\leq\ell(n)}$ as $x^{(n)}_{0},x^{(n)}_{1},x^{(n)}_{2},\ldots$
according to the lexicographic order. We define $Q_{n}$ to be composed of all
strings of the form $[\>\begin{subarray}{c}x_{i}^{(n)}\\\
a_{i}\end{subarray}]$, where (i) $a_{i}=+1$ if $x^{(n)}_{i}\in L_{n}^{(+)}$,
(ii) $a_{i}=-1$ if $x^{(n)}_{i}\in L_{n}^{(-)}$, and (iii) $a_{i}=0$
otherwise. Let us design a 1dfa $M_{n}$ to read an entire input, say, $x$,
determine $i$ satisfying $x=x^{(n)}_{i}$, and accept (resp., reject) $x$ if
$a_{i}=+1$ (resp., $a_{i}=-1$). The family ${\cal
M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ clearly has polynomial size. Since ${\cal M}$
solves ${\cal L}$, ${\cal L}$ belongs to $1\mathrm{D}$. ∎

Next, we look into the case of polynomial ceiling. As our main result of this
work, we prove the collapse of $2\mathrm{N}/\mathrm{poly}$ down to
$2\mathrm{U}/\mathrm{poly}$. Our proof is motivated by a simulation technique
of [16].

###### Theorem 4.2

$2\mathrm{U}/\mathrm{poly}=2\mathrm{FewU}/\mathrm{poly}=2\mathrm{Few}/\mathrm{poly}=2\mathrm{N}/\mathrm{poly}$.

We stress that Theorem 4.2 does not seem to imply
$2\mathrm{N}/\mathrm{subexp}=2\mathrm{U}/\mathrm{subexp}$,
$2\mathrm{N}/\mathrm{exp}=2\mathrm{U}/\mathrm{exp}$, and
$2\mathrm{N}=2\mathrm{U}$. Hence, those equalities are still unknown to hold.

For two other nonuniform state complexity classes, $2\mathrm{ReachFewU}$ and
$2\mathrm{ReachFew}$, we obtain the following relationships, depicted in
Figure 1.

###### Corollary 4.3

$2\mathrm{D}/\mathrm{poly}\subseteq 2\mathrm{ReachU}/\mathrm{poly}\subseteq
2\mathrm{ReachFewU}/\mathrm{poly}\subseteq
2\mathrm{ReachFew}/\mathrm{poly}\subseteq 2\mathrm{U}/\mathrm{poly}$.

In what follows, we intend to provide the proof of Theorem 4.2.

Proof of Theorem 4.2.  Because $2\mathrm{U}/\mathrm{poly}\subseteq
2\mathrm{FewU}/\mathrm{poly}\subseteq 2\mathrm{Few}/\mathrm{poly}\subseteq
2\mathrm{N}/\mathrm{poly}$, it suffices to prove the inclusion
$2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}/\mathrm{poly}$, which is
equivalent to $2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}$. Hereafter, we
intend to prove that $2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}$.

It is shown in [11] (re-proven in [24] by a different argument) that
$2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{D}$ iff
$\mathrm{NL}\subseteq\mathrm{L}/\mathrm{poly}$. In a similar vein, we claim
the following.

###### Claim 4.4

$\mathrm{NL}\subseteq\mathrm{UL}/\mathrm{poly}$ implies
$2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}$.

Assume that Claim 4.4 is true. Since Reinhardt and Allender [16] proved the
inclusion $\mathrm{NL}\subseteq\mathrm{UL}/\mathrm{poly}$, we instantly obtain
$2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}$. Therefore, we aim at proving
Claim 4.4 by adopting the proof technique of [21, 23, 24] based on
parameterized decision problems. Yamakami [21] first discovered a close
connection between polynomial-size finite automata families and parameterized
decision problems. Now, let us introduce the necessary notion of parameterized
decision problems.

A _parameterized decision problem_ over alphabet $\Sigma$ is a pair $(L,m)$ of
a language $L$ over $\Sigma$ and a size parameter $m$, which is a function
from $\Sigma^{*}$ to $\mathbb{N}$. A _log-space size parameter_ $m$ must
satisfy the additional condition that there exists a log-space deterministic
Turing machine (DTM) $M$ for which $M$ on any input $x$ produces $1^{m(x)}$ on
a write-once666An output tape is _write once_ if (1) its tape head never moves
back to the left and (2) whenever the tape head writes a non-blank symbol onto
the put tape, it must move to the right next blank cell. output tape. An
_advice function_ $h$ is a function from $\mathbb{N}$ to $\Gamma^{*}$ for a
certain alphabet $\Gamma$ and it is said to be _polynomially bounded_ if
$|h(n)|\leq p(n)$ holds for all $n\in\mathbb{N}$ for an appropriately chosen
polynomial $p$. A parameterized decision problem $(L,m)$ belongs to
$\mathrm{PHSP}$ if $m$ is _polynomially honest_ (that is, there exists a
polynomial $q$ such that $|x|\leq q(m(x))$ for all strings $x$). The notation
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}$ denotes the class composed of
all parameterized decision problems $(L,m)$ with log-space size parameters
$m$, such that, for each $(L,m)$, there exists a nondeterministic Turing
machine (NTM) $M$ equipped with read-only input and advice tapes and a
polynomially-bounded advice function $h$ for which $M$ solves $L$ in time
$m(x)^{O(1)}$ using space $O(\log{m(x)})$ with free access to advice strings
$h(|x|)$ written on the advice tape, where $x$ is a “symbolic” input.
Similarly, $\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$ is defined using
“unambiguous” NTMs (or UTM, for short) instead of NTMs. The reader refers to
[26, 21, 24] for more information on parameterized decision problems.

Claim 4.4 follows immediately from two assertions in the following claim.
Given a language $L$ over alphabet $\Sigma$, its complement $\Sigma^{*}-L$ is
succinctly denoted $\overline{L}$.

###### Claim 4.5

  1. 1.

$\mathrm{NL}\subseteq\mathrm{UL}/\mathrm{poly}$ implies
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$.

  2. 2.

$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$
implies $2\mathrm{N}/\mathrm{poly}\subseteq 2\mathrm{U}$.

To close the proof of Theorem 4.2, in what follows, we wish to prove Claim
4.5.

(1) Let us begin with the proof of Claim 4.5(1). Assume that
$\mathrm{NL}\subseteq\mathrm{UL}/\mathrm{poly}$. Note that
$\mathrm{NL}\subseteq\mathrm{UP}/\mathrm{poly}$ implies
$\mathrm{NL}/\mathrm{poly}\subseteq\mathrm{UL}/\mathrm{poly}$. Let us consider
an arbitrary parameterized decision problem $(L,m)$ in
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}$ with a log-
space size parameter $m:\Sigma^{*}\to\mathbb{N}$ and a language $L$ over
alphabet $\Sigma$. Take a polynomially-bounded advice function $h$ and an NTM
$M_{0}$ such that $M_{0}$ recognizes $\\{(x,h(|x|))\mid x\in L\\}$ in time
$(m(x))^{O(1)}$ and space $O(\log{m(x)})$. We wish to verify that
$(L,m)\in\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$. For this purpose, we
define $L_{n}^{(+)}=L\cap\Sigma_{n}$ and
$L_{n}^{(-)}=\overline{L}\cap\Sigma_{n}$, where
$\Sigma_{n}=\\{x\in\Sigma^{*}\mid m(x)=n\\}$. We further set ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$.

Since $m$ is polynomially honest, we take a polynomial $q$ such that $|x|\leq
q(m(x))$ for all $x$. We write $K^{\prime}$ for the set $\\{(x,1^{t})\mid x\in
L,t\in\mathbb{N},m(x)\leq t\\}$ and claim that
$K^{\prime}\in\mathrm{NL}/\mathrm{poly}$. Consider the following algorithm. On
input $(x,1^{t})$, we check if $m(x)\leq t$ using log space. This is possible
because $m$ is log-space computable. If $m(x)>t$, then we reject the input;
otherwise, we simulate $M_{0}$ on $(x,h(|x|))$. Clearly, this algorithm
recognizes $K^{\prime}$. This algorithm can be realized by an appropriate NTM
running in time $(|x|t)^{O(1)}$ and space $O(\log{|x|t})$ with the help of
$h$. Since $|(x,1^{t})|=O(|x|+t)$, $K^{\prime}$ belongs to
$\mathrm{NL}/\mathrm{poly}$.

Since $\mathrm{NL}/\mathrm{poly}\subseteq\mathrm{UL}/\mathrm{poly}$ by our
assumption, $K^{\prime}$ must be in $\mathrm{UL}/\mathrm{poly}$. Take a UTM
$M$, an advice function $g$, a logarithmic function $\ell^{\prime}$ such that
$M$ recognizes $K^{\prime}$ using at most $\ell^{\prime}(|z|)$ space with an
access to $g(|z|)$, where $z$ indicates a “symbolic” input. We then design a
new NTM $N$ for $(K,m^{\prime})$ as follows. Define
$g^{\prime}(|x|)=g(|(x,1^{t})|)$ for all $x\in\Sigma^{*}$. On input $x$,
compute $n=m(x)$, and run $M$ on $(x,1^{n})$ with $g^{\prime}(|x|)$. Note that
$N$’s space usage is $O(\ell^{\prime}(|x|+n)+\log|x|)\subseteq
O(\log(q(m(x))+n)+\log{|x|})\subseteq O(\log{m(x)})$ since $q$ is a polynomial
satisfying $|x|\leq q(m(x))$. This shows that
$(L,m)\in\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$.

By the definition of $L$, ${\cal L}$ falls into $2\mathrm{N}$. Let
$M_{n}=(Q_{n},\Sigma,\\{\rhd,\lhd\\},\delta_{n},q_{0,n},Q_{acc,n},Q_{rej,n})$.
Consider a computation graph $G_{n}=(V_{n},E_{n})$ of $M_{n}$ on each input of
length at most $f(n)$.

A configuration of $M_{n}$ is of the form $(q,l)$, which indicates that
$M_{n}$ is in state $q$ and its tape head scans cell $l$. We view an
$(f(n)+2)$-partite graph of the following form:
$V_{n}=Q_{n}\times[0,f(n)+1]_{\mathbb{Z}}$ and
$((q,l),(q^{\prime},l^{\prime}))\in E_{n}$ iff
$(q^{\prime},d)\in\delta_{n}(q,x_{(l)})$ and $l^{\prime}=l+d$.

(2) Next, we wish to prove Claim 4.5(2). For its proof, we loosely follow an
argument made in the proof of [24, Proposition 5.1]. A key to this argument is
Claim 4.6 that ties between parameterized decision problems and families of
promise problems. To describe the claim, we need to recall the following
terminology used in [23, 24].

Let $(L,m)$ denote a parameterized decision problem over alphabet $\Sigma$ and
let ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be any family
of promise problems. We say that ${\cal L}$ is _induced from_ $(L,m)$ if, for
any index $n\in\mathbb{N}$, $L_{n}^{(+)}=L\cap\Sigma_{n}$ and
$L_{n}^{(-)}=\overline{L}\cap\Sigma_{n}$, where $\Sigma_{n}$ denotes the set
$\\{x\in\Sigma^{*}\mid m(x)=n\\}$. For two families of promise problems ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ and ${\cal K}=\\{({\cal
K}_{n}^{(+)},{\cal K}_{n}^{(-)})\\}_{n\in\mathbb{N}}$, we say that ${\cal K}$
is an _extension_ of ${\cal L}$ if, for any index $n\in\mathbb{N}$,
$L_{n}^{(+)}\subseteq K_{n}^{(+)}$ and $L_{n}^{(-)}\subseteq K_{n}^{(-)}$. We
say that ${\cal L}$ is _$\mathrm{L}$ -good_ if the set $\\{1^{n}\\#x\mid
n\in\mathbb{N},x\in L_{n}^{(+)}\cap L_{n}^{(-)}\\}$ belongs to $\mathrm{L}$. A
collection ${\cal F}$ of families of promise problems is _$\mathrm{L}$ -good_
if all elements of ${\cal F}$ has an $\mathrm{L}$-good extension in ${\cal
F}$. From a family ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$, we introduce
$K_{n}^{(+)}=\\{1^{n}\\#x\mid x\in L_{n}^{(+)}\\}$ and
$K_{n}^{(-)}=\\{1^{n}\\#x\mid x\notin L_{n}^{(+)}\\}\cup S_{n}$, where
$\Sigma_{\\#}=\Sigma\cup\\{\\#\\}$ and $S_{n}=\\{z\\#x\mid
z\in\Sigma^{n}-\\{1^{n}\\},x\in(\Sigma_{\\#})^{*}\\}\cup\Sigma^{n}$. We say
that $(K,m)$ is _induced from_ ${\cal L}$ if $K$ equals
$\bigcup_{n\in\mathbb{N}}K_{n}^{(+)}$ and $m:(\Sigma_{\\#})^{*}\to\mathbb{N}$
satisfies the following: for any string $w$ of the form $1^{n}\\#x$ with $x\in
L_{n}^{(+)}\cup L_{n}^{(-)}$, $m(w)=n$, and for all other strings $w$,
$m(w)=|w|$. Note that $\overline{K}$ equals
$\bigcup_{n\in\mathbb{N}}K_{n}^{(-)}$. See [24] for more information.

The $\mathrm{L}$-goodness of $2\mathrm{N}/\mathrm{poly}$ was shown in [24]. It
is, however, unclear that $2\mathrm{U}/\mathrm{poly}$ is also
$\mathrm{L}$-good. We then describe a key statement, Claim 4.6.

###### Claim 4.6

Let $({\cal C},{\cal
D})\in\\{(\mathrm{NL},2\mathrm{N}),(\mathrm{UL},2\mathrm{U})\\}$. Let ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ denote any family of
promise problems and let $(L,m)$ and $(K,m)$ be any two parameterized decision
problems with the common logspace size parameter $m$. (a) If ${\cal L}$ is
induced from $(L,m)$, then $(L,m)\in\mathrm{para}\mbox{-}{\cal
C}/\mathrm{poly}\cap\mathrm{PHSP}$ iff ${\cal L}\in{\cal D}/\mathrm{poly}$.
(b) If ${\cal L}$ is $\mathrm{L}$-good and $(K,m)$ is induced from ${\cal L}$,
then $(K,m)\in\mathrm{para}\mbox{-}{\cal C}/\mathrm{poly}\cap\mathrm{PHSP}$
iff ${\cal L}\in{\cal D}/\mathrm{poly}$.

###### Proof.

The case of ${\cal C}=\mathrm{NL}$ and ${\cal D}=2\mathrm{N}$ was proven in
[24]. Now, let us consider the case of ${\cal C}=\mathrm{UL}$ and ${\cal
D}=2\mathrm{U}$. The proof idea is similar to the first case of ${\cal
C}=\mathrm{NL}$ and ${\cal D}=2\mathrm{N}$.

(a) Let ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ denote any
family of promise problems induced from $(L,m)$. Assume that
$(L,m)\in\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}\cap\mathrm{PHSP}$.
There are an advice function $h$ of output size $m(x)^{O(1)}$ and a UTM $M$
that solves $(L,m)$ in time $m(x)^{O(1)}$ using space $O(\log{m(x)})$. Since
$m$ is a logspace size parameter, it is polynomially bounded. Take a suitable
polynomial $q$ satisfying $m(x)\leq q(|x|)$ for all $x$. The space usage of
$M$ is thus upper-bounded by $O(\log|x|)$. Note that $\Sigma_{n}=\\{x\mid
m(x)=n\\}\subseteq\Sigma^{\leq q(n)}$. We also assume that $|h(i)|\leq
p(m(x))$. Hereafter, we intend to verify that ${\cal L}\in
2\mathrm{U}/\mathrm{poly}$.

We then construct a 1nfa $N_{n}$ that takes $x$ as an input and simulates $M$
on input $(x,h(|x|))$. For this purpose, we embed the information on
$(h_{i1},h_{i2},\ldots,h_{ik_{i}})$ for $h(i)=h_{i1}h_{i2}\cdots h_{i|h(i)|}$
into $|h(i)|$ inner states of $N_{n}$ so that it can recover $h(i)$ from these
inner states. It follows that $N_{n}$ is unambiguous on $\Sigma_{n}$. Since
$\\{N_{n}\\}_{n\in\mathbb{N}}$ solves ${\cal L}$, we conclude that ${\cal
L}\in 2\mathrm{U}/\mathrm{poly}$.

Next, we assume that ${\cal L}\in 2\mathrm{U}/\mathrm{poly}$. Take a family
${\cal N}=\\{N_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 1ufa’s solving
${\cal L}$. We then define an NTM $M$ that recognizes $(L,m)$ with the help of
an advice function $h$. We encode the transitions of $N_{n}$ into an advice
string. On input $x$, compute $n=m(x)$, and simulate $N_{n}$ on $x$. It then
follows that $M$ is unambiguous and recognizes $(L,m)$.

(b) Assume that ${\cal L}$ is $\mathrm{L}$-good and that $(K,m)$ is induced
from ${\cal L}$. If
$(K,m)\in\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}\cap\mathrm{PHSP}$,
then we take an advice function $h$ of output size $m(x)^{O(1)}$ and a UTM $M$
for which $M$ solves $(K,m)$ in time $m(x)^{O(1)}$ using space $O(\log{m(x)})$
with the help of $h$. We construct a 1nfa $N_{n}$ that behaves as follows.
Recall from the proof of (a) the embedding of $h(i)$ into $|h(i)|$ inner
states. On input $x$, recover $h(|x|)$ from $N_{n}$’s inner states, and
simulate $M$ on $(1^{n}\\#x,h(|x|))$. This implies that $N_{n}$ solves
$(L_{n}^{(+)},L_{n}^{(-)})$.

On the contrary, assume that ${\cal L}\in 2\mathrm{U}/\mathrm{poly}$ and take
a family $\\{N_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 1ufa’s solving
${\cal L}$. Since $N_{n}$ is of polynomial size, we can encode $N_{n}$ into an
advice string $\alpha_{n}$ of polynomial length. Since ${\cal L}$ has a
polynomial ceiling, take a constant $k\geq 1$ satisfying $L_{n}^{(+)}\cup
L_{n}^{(-)}\subseteq\Sigma^{\leq n^{k}+k}$ for any $n\in\mathbb{N}$. We then
construct an NTM $M$ such that, on input $y$, check if $y$ has the form
$1^{n}\\#x$ with $|x|\leq n^{k}+k$. If so, simulate $N_{n}$ on $x$. Since
$m(y)=n$, it follows that $|y|=n+|x|+1\leq n^{k+1}+k\leq m(y)^{k+1}+k$.
Otherwise, reject $x$ immediately. This machine $M$ is unambiguous and also
recognizes $K$ in time polynomial in $m(y)$ using space logarithmic in $m(y)$.
∎

Assume that
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$.
Let ${\cal L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ be an
arbitrary element of $2\mathrm{N}/\mathrm{poly}$ and take two polynomials
$p,q$ and a family ${\cal M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of 2nfa’s that
solves ${\cal L}$ with the following properties: each $M_{n}$ has at most
$p(n)$ inner states and $\Sigma_{n}$ ($=L_{n}^{(+)}\cup L_{n}^{(-)}$) is
included in $\Sigma^{\leq q(n)}$. Hereafter, we wish to prove that ${\cal L}$
belongs to $2\mathrm{U}$.

For each index $n\in\mathbb{N}$, we define $K_{n}^{(+)}=\\{1^{n}\\#x\mid x\in
L_{n}^{(+)}\\}$ and $K_{n}^{(-)}=\\{1^{n}\\#x\mid x\in
L_{n}^{(-)}\\}\cup\\{z\\#x\mid
z\in\Sigma^{n}-\\{1^{n}\\},x\in\Sigma^{*}_{\\#}\\}\cup\\{z\mid
z\in\Sigma^{n}\\}$, where $\Sigma_{\\#}=\Sigma\cup\\{\\#\\}$. We set
$K=\bigcup_{n\in\mathbb{N}}K_{n}^{(+)}$ and
$K^{c}=\bigcup_{n\in\mathbb{N}}K_{n}^{(-)}$. It then follows that $K\cup
K^{c}=\Sigma^{*}_{\\#}$ and $K\cap K^{c}=\varnothing$; thus, $K^{c}$ coincides
with the complement $\overline{K}$ of $K$. We define $m^{\prime}(w)=n$ if
$w=1^{n}\\#x$ for a certain $x\in L_{n}^{(+)}\cup L_{n}^{(-)}$ and
$m^{\prime}(w)=|w|$ otherwise. Note that $m^{\prime}$ is log-space computable
and also polynomially honest. Since $(L_{n}^{(+)},L_{n}^{(-)})$ is solved by
$M_{n}$ for each $n\in\mathbb{N}$, $K$ is solvable nondeterministically in
time $(|x|m(x))^{O(1)}$ and space $O(\log{m(x)})$ with the use of an
appropriate polynomial-size advice function. Thus, $(K,m^{\prime})$ belongs to
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}$.

The assumption
$\mathrm{para}\mbox{-}\mathrm{NL}/\mathrm{poly}\cap\mathrm{PHSP}\subseteq\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$
makes $(K,m^{\prime})$ fall into
$\mathrm{para}\mbox{-}\mathrm{UL}/\mathrm{poly}$. Take an advice function $h$
and a UTM $N$ that solve $K$ in time $(|x|m^{\prime}(x))^{O(1)}$ and space
$O(\log{m^{\prime}(x)})$. Consider the algorithm that, on input $x$ with index
$n\in\mathbb{N}$, generate both $1^{n}\\#x$ and $h(|x|)$ and then run $N$ on
$(1^{n}\\#x,h(|x|))$ to produce an outcome. An appropriate unambiguous 2nfa,
say, $N^{\prime}_{n}$ can realize this algorithm since we can store $h(|x|)$
as a series of inner states. We thus conclude that $N^{\prime}_{n}$ solves
$(L_{n}^{(+)},L_{n}^{(-)})$. Therefore, ${\cal L}$ belongs to $2\mathrm{U}$.

This completes the proof of Theorem 4.2. $\Box$

###  4.2 Case of No Ceiling Restriction

We have discussed the case of bounded ceilings in Section 4.1. We next turn
our attention to the case of no ceiling restriction. Kapoutsis [11] earlier
demonstrated that $2\mathrm{N}\subseteq 2\mathrm{D}$ holds exactly when
$2\mathrm{N}/\mathrm{supexp}\subseteq 2\mathrm{D}$, where “$\mathrm{supexp}$”
denotes the set of all super exponentials on $\mathbb{N}$. Similarly, we can
assert that, even in our unambiguity/fewness setting, the case of no ceiling
restriction on families of promise problems is logically equivalent to the
case of $\mathrm{supexp}$-ceiling restriction on those families. More
formally, we wish to prove the following.

###### Theorem 4.7

Let ${\cal A}$ denote the set
$\\{\mathrm{D},\mathrm{ReachU},\mathrm{ReachFewU},\mathrm{ReachFew},\mathrm{U},\mathrm{FewU},\mathrm{Few},\mathrm{N}\\}$.
For any two classes ${\cal C},{\cal D}$ taken from ${\cal A}$, it follows that
$2{\cal C}\subseteq 2{\cal D}$ iff $2{\cal C}/\mathrm{supexp}\subseteq 2{\cal
D}$.

The proof of this theorem can be obtained by slightly modifying the proof in
[11]. For the sake of completeness, nevertheless, we include the proof of the
theorem.

For a finite automaton $M$, the notation $L(M)$ means the set of all strings
accepted by $M$. In the following proof, for simplicity, we assume without
loss of generality that 2nfa’s make their tape head return to the start cell
when they halt.

Proof of Theorem 4.7.  Let ${\cal C},{\cal D}$ be any classes in ${\cal A}$.
Since $2{\cal C}/\mathrm{supexp}\subseteq 2{\cal C}$, it is obvious that
$2{\cal C}\subseteq 2{\cal D}$ implies $2{\cal C}/\mathrm{supexp}\subseteq
2{\cal D}$. In what follows, we intend to prove the converse. Assuming that
$2{\cal C}/\mathrm{supexp}\subseteq 2{\cal D}$, we aim at proving that $2{\cal
C}\subseteq 2{\cal D}$. Let $f(n)$ denote any function in $\mathrm{supexp}$.
It then follows that, for any polynomial $q$, $f(n)>2^{q(n)}$ holds for all
but finitely many numbers $n\in\mathbb{N}$. Let ${\cal
L}=\\{(L_{n}^{(+)},L_{n}^{(-)})\\}_{n\in\mathbb{N}}$ denote any family of
promise problems in $2{\cal C}$ and take a family ${\cal
N}=\\{N_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 2nfa’s that solves ${\cal
L}$, where every $N_{n}$ must satisfy the condition imposed by the definition
of $2{\cal C}$. For each $n\in\mathbb{N}$, let
$N_{n}=(Q^{\prime}_{n},\Sigma,\\{\rhd,\lhd\\},\delta^{\prime}_{n},q^{\prime}_{0,n},Q^{\prime}_{acc,n},Q^{\prime}_{rej,n})$.
There exists a polynomial $q$ satisfying $|Q^{\prime}_{n}|\leq q(n)$ for all
$n\in\mathbb{N}$.

Fix $n$ arbitrarily. We expand $(L_{n}^{(+)},L_{n}^{(-)})$ to the “language”
$L(N_{n})$ induced by $N_{n}$. Notice that $L_{n}^{(+)}\subseteq L(N_{n})$ and
$L_{n}^{(-)}\subseteq\overline{L(N_{n})}$. For convenience, we write
$N_{n}(x)$ to denote the outcome (i.e., acceptance or rejection) of $N_{n}$ on
input $x$. From this language $L(N_{n})$, we define another promise problem
$(K_{n}^{(+)},K_{n}^{(-)})$ by setting $K_{n}^{(+)}=\\{x\in
L(N_{n})\mid|x|\leq f(n)\\}$ and
$K_{n}^{(-)}=\\{x\in\overline{L(N_{n})}\mid|x|\leq f(n)\\}$. Let us consider
the family ${\cal K}=\\{(K_{n}^{(+)},K_{n}^{(-)})\\}_{n\in\mathbb{N}}$. Since
${\cal K}$ has an $f(n)$-ceiling, ${\cal K}$ must be in $2{\cal C}/f(n)$,
which is further included in $2{\cal C}/\mathrm{supexp}$ since
$f\in\mathrm{supexp}$.

By our assumption, ${\cal K}$ belongs to $2{\cal D}$. Take a family ${\cal
M}=\\{M_{n}\\}_{n\in\mathbb{N}}$ of polynomial-size 2nfa’s with
$M_{n}=(Q_{n},\Sigma,\\{\rhd,\lhd\\},\delta_{n},q_{0,n},Q_{acc,n},Q_{rej,n})$
that solves ${\cal K}$, where $|Q_{n}|\leq p(n)$ holds for a fixed polynomial
$p$ independent of $n$ and each $M_{n}$ satisfies the condition imposed for
$2{\cal D}$. Remember that $M_{n}$ may take strings of arbitrary lengths as
its inputs. However, for any input $x$ of length at most $f(n)$, $M_{n}(x)$
coincides with $N_{n}(x)$ by the definition of ${\cal K}$. We then compare
between the behaviors of $M_{n}$ and $N_{n}$. Define
$r(n)=2(p(n)^{2}+q(n)^{2})$ for all $n\in\mathbb{N}$, which is a polynomial
satisfying $2(|Q_{n}|^{2}+|Q^{\prime}_{n}|^{2})\leq r(n)$. We then claim the
following statement concerning the “discrepancy” set $A=\\{n\in\mathbb{N}\mid
L(M_{n})\neq L(N_{n})\\}$.

###### Claim 4.8

$A\subseteq\\{n\in\mathbb{N}\mid 2^{r(n)}\geq f(n)\\}$.

###### Proof.

We first show that, if $L(M_{n})\neq L(N_{n})$, then there exists a string $y$
of length at most $2^{r(n)}$ for which $M_{n}(y)\neq N_{n}(y)$. If this is
true, then it follows from $M_{n}(y)\neq N_{n}(y)$ that $|y|>f(n)$. We then
obtain $2^{r(n)}\geq f(n)$. In conclusion, $A$ is a subset of
$\\{n\in\mathbb{N}\mid 2^{r(n)}\geq f(n)\\}$.

Fix an arbitrary index $n\in A$ and take the shortest string $x$ satisfying
$M_{n}(x)\neq N_{n}(x)$. Recall from Section 2.2 the notion of critical
computation path. From $(M_{n},N_{n},x)$, we obtain two critical computation
paths $\gamma_{M_{n}}(x)$ and $\gamma_{N_{n}}(x)$ associated with $M_{n}$ and
$N_{n}$, respectively. By Lemma 2.1, the crossing sequence at any boundary of
$\gamma_{M_{n}}(x)$ (resp., $\gamma_{N_{n}}(x)$) has length at most $2|Q_{n}|$
(resp., $2|Q^{\prime}_{n}|$).

We define $D$ to be the collection of all pairs $(\alpha,\alpha^{\prime})$
such that $\alpha$ (resp., $\alpha^{\prime}$) is a crossing sequence of length
at most $2|Q_{n}|$ (resp., $2|Q^{\prime}_{n}|$) of $\gamma_{M_{n}}(x)$ (resp.,
$\gamma_{N_{n}}(x)$) at the same boundary. Note that
$|D|\leq|Q_{n}|^{2|Q_{n}|}\cdot|Q^{\prime}_{n}|^{2|Q^{\prime}_{n}|}\leq
2^{2p(n)^{2}+2q(n)^{2}}=2^{r(n)}$. Thus, if $|x|\geq 2^{r(n)}+1$, then there
exist a distinct pair $(s_{1},s_{2})$ and another pair
$(\alpha,\alpha^{\prime})$ for which $\gamma_{M_{n}}(x)$ and
$\gamma_{N_{n}}(x)$ have a crossing sequence pair $(\alpha,\alpha^{\prime})$
in $D$ at the both boundaries $s_{1}$ and $s_{2}$. Therefore, given any input
$x$ with $|x|\geq 2^{r(n)}+1$, there exists another input $y$ of length at
most $2^{r(n)}$ for which $M_{n}(x)=M_{n}(y)$ and $N_{n}(x)=N_{n}(y)$. From
this, we obtain $M_{n}(y)\neq N_{n}(y)$. Since $|y|<|x|$, this contradicts the
minimality of $x$. ∎

Finally, we modify $M_{n}$ into $M^{\prime}_{n}$ in order to solve
$(L_{n}^{(+)},L_{n}^{(-)})$. By the choice of $f$, $\\{n\in\mathbb{N}\mid
2^{r(n)}\geq f(n)\\}$ is a finite set, and thus $A$ is also a finite set. Let
$c$ denote the largest number in $A$. Let $n$ be any number in $\mathbb{N}$.
If $n\in A$, then we take a 1dfa that exactly simulates $N_{n}$ with
$2^{O(|Q^{\prime}_{n}|)}$ inner states and we set $M^{\prime}_{n}$ to be this
1dfa. It is important to remark that, since $1\mathrm{D}\subseteq 2{\cal D}$,
$M^{\prime}_{n}$ is a 2nfa satisfying the condition imposed for $2{\cal D}$.
Otherwise, we define $M^{\prime}_{n}$ to be exactly $M_{n}$. Since
$L(M_{n})=L(N_{n})$ for all $n>c$, the state complexity of $M^{\prime}_{n}$ is
upper-bounded by a certain constant, independent of $n$. Therefore,
$M^{\prime}_{n}$ correctly solves $(L_{n}^{(+)},L_{n}^{(-)})$, as requested.
$\Box$

##  5 A Short Discussion and Open Problems

The _theory of nonuniform polynomial state complexity_ dates back to the late
1970s [3, 17] and it seems to have been left unattended until the late 2000s
in the field of automata and computational complexity. This intriguing theory
was rediscovered in 2009 [9] and it has recently gained its pace with a series
of studies [7, 10, 11, 12, 21, 22, 23, 24, 27].

In this work, we have attempted to continue the investigation of the
computational complexity of families of various types of finite automata of
polynomial state complexity. In particular, we have concentrated on nonuniform
families of polynomial-size nondeterministic finite automata with
unambiguity/fewness conditions imposed on their computation graphs and
accepting computation paths. Inspired by [15], we have studied in this work
six complexity classes of families of promise problems solvable by those
specific finite automaton families. When tape heads of underlying finite
automata are limited to move in only one direction, we have shown mutual class
separations, namely, most of those complexity classes are distinct from each
other. On the contrary, when the tape heads are allowed to move in both
directions, four of the six complexity classes have been shown to collapse.
All those results have been illustratively summarized in Figure 1.

As for problems left untold in this work, we wish to list four relevant topics
for the interested reader.

  1. 1.

It is important to point out that Figure 1 is not yet complete. We therefore
need to complete this figure by filling its missing parts. For instance, is it
true that $1\mathrm{U}\nsubseteq 1\mathrm{ReachFewU}$ or even
$1\mathrm{U}\nsubseteq 1\mathrm{ReachFew}$? Does $1\mathrm{ReachFew}\nsubseteq
1\mathrm{FewU}$ hold?

  2. 2.

We have shown that $2\mathrm{N}/\mathrm{poly}$ coincides with
$2\mathrm{U}/\mathrm{poly}$, but this result does not seem to extend to the
collapse of $2\mathrm{N}/\mathrm{poly}$ down to
$2\mathrm{ReachFew}/\mathrm{poly}$ (or $2\mathrm{ReachFewU}/\mathrm{poly}$ or
even $2\mathrm{ReachU}/\mathrm{poly}$). Does such a collapse actually occur?

  3. 3.

The choice of ceiling (e.g., polynomial and exponential) may affect the
computational strengths of nonuniform state complexity classes. When we
replace “polynomial ceilings” by “exponential ceilings”, for instance, is it
true that $2\mathrm{N}/\mathrm{exp}\subseteq 2\mathrm{U}$? Is it also true
that $2\mathrm{ReachFew}/\mathrm{exp}\subseteq 2\mathrm{ReachFewU}$?

  4. 4.

Recently, as a natural extension of finite automata, nonuniform families of
pushdown automata were studied in [23]. We write $2\mathrm{DPD}$ for the
collection of all families of promise problems solvable by nonuniform families
of 2-way pushdown automata having polynomial stack-state complexity. For more
precise definition, refer to [23]. It is unknown that $2\mathrm{N}\subseteq
2\mathrm{DPD}$. For other low complexity classes, such as
$2\mathrm{ReachFewU}$ and $2\mathrm{ReachFew}$, is it true that
$2\mathrm{ReachFewU}\subseteq 2\mathrm{DPD}$ or even
$2\mathrm{ReachFew}\subseteq 2\mathrm{DPD}$?

  5. 5.

When a tape head of a one-way finite automaton is further allowed to stay
still at any moment (that is, makes $\varepsilon$-moves), we empathetically
call an associated machine a _1.5-way finite automaton_. It is shown in [24]
that $1\mathrm{D}=\mathrm{1.5D}$ but $1\mathrm{BQ}\neq\mathrm{1.5BQ}$, where
$1\mathrm{BQ}$ and $\mathrm{1.5BQ}$ are defined by bounded-error 1-way and
1.5-way quantum finite automata having polynomially many inner states. It
seems interesting to ask types of finite automata make the 1.5-way head move
different from the 1-way head move.

## References

  * [1] E. Allender. The compelxity of sparse sets in P. In the Proc. of the 1st Structure in Complexity Theory Conference, LNCS, vol. 223, pp. 1–11, Springer (1986)
  * [2] E. Allender and R. Rubinstein. P-printable sets. SIAM J. Comput. 17, 1193–1202 (1988)
  * [3] P. Berman and A. Lingas. On complexity of regular languages in terms of finite automata. Report 304, Institute of Computer Science, Polish Academy of Science, Warsaw (1977)
  * [4] C. Bourke, R. Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Trans. Comput. Theory 1, 1–17 (2009)
  * [5] G. Buntrock, B. Jenner, K. Lange, and P. Rossmanith. Unambiguity and fewness for logarithmic space. In the Proc. of the 8th International Conference on Fundamentals of Computation Theory (FCT’91), Lecture Notes in Computer Science, vol. 529, pp. 168–179, Springer (1991)
  * [6] B. Garvin, D. Stolee, R. Tewari, and V. Vinodchandran. ReachFewL = ReachUL. Manuscript (2011)
  * [7] V. Geffert. An alternating hierarchy for finite automata. Theor. Comput. Sci. 445, 1–24 (2012).
  * [8] N. Immerman. Nondeterministic space is closed under complement. SIAM J. Comput. 17 (1988) 935–938.
  * [9] C. A. Kapoutsis. Size complexity of two-way finite automata. In the Proc. of the 13th International Conference on Developments in Language Theory (DLT 2009), Lecture Notes in Computer Science, vol. 5583, pp. 47–66, Springer (2009)
  * [10] C. A. Kapoutsis. Minicomplexity. J. Automat. Lang. Combin. 17, 205–224 (2012)
  * [11] C. A. Kapoutsis. Two-way automata versus logarithmic space. Theory Comput. Syst. 55, 421–447 (2014)
  * [12] C. A. Kapoutsis and G. Pighizzini. Two-way automata characterizations of L/poly versus NL. Theory Comput. Syst. 56, 662–685 (2015)
  * [13] R. M. Karp and R. J. Lipton. Turing machines that take advice. L’Enseigrement Mathématique 28, 191–209 (1982)
  * [14] M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Third edition. Springer (2008)
  * [15] A. Pavan, R. Tewari, N. V. Vinodchandran. On the power of unambiguity in logspace. Computational Complexity 21, 643–670 (2012)
  * [16] K. Reinhardt and E. Allender. Making nondeterminism unambiguous. SIAM J. Comput. 29, 1118–1131 (2000)
  * [17] W. J. Sakoda and M. Sipser. Nondeterminism and the size of two-way finite automata. In the Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 275–286 (1978).
  * [18] R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Inform. 26 (1988) 279–284.
  * [19] L. Valiant. The relative complexity of checking and evaluating. Inform. Process. Lett. 5, 20–23 (1976)
  * [20] T. Yamakami. The roles of advice to one-tape linear-time Turing machines and finite automata. Int. J. Found. Comput. Sci. 21 (2010) 941–962.
  * [21] T. Yamakami. State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis. Theor. Comput. Sci. 798, 2–22 (2019). A preliminary report appeared in the Proc. of DCFS 2018, LNCS, vol. 10952, pp. 237–249, Springer (2018)
  * [22] T. Yamakami. Relativizations of nonuniform quantum finite automata families. In the Proc. of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019), Lecture Notes in Computer Science, vol. 11493, pp. 257–271, Springer (2019)
  * [23] T. Yamakami. Parameterizations of logarithmic-space reductions, stack-state complexity of nonuniform families of pushdown automata, and a road to the LOGCFL$\subseteq$LOGDCFL/poly question. Manuscript, available at arXiv:2108.12779 (2021)
  * [24] T. Yamakami. Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice. Inform. Comput. 286, article 104783 (2022). A preliminary version apperaed in the Proc. of LATA 2019, LNCS, vol. 11417, pp. 134–145, Springer (2019)
  * [25] T. Yamakami. Unambiguity and fewness for nonuniform families of polynomial-size nondeterministic finite automata. In the Proc. of the 16th International Conference on Reachability Problems (RP 2022), Lecture Notes in Computer Science, vol. 13608, pp. 77–92, Springer Cham (2022)
  * [26] T. Yamakami. The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. J. Comput. System Sci. 136, 88–112 (2023). A preliminary report appeared in the Proc. of MFCS 2017, LIPIcs, vol. 83, pp. 62:1–62:14 (2017)
  * [27] T. Yamakami. Power of counting by nonuniform families of polynomial-size finite automata. In the Proc. of the 24th International Symposium on Fundamentals of Computer Science (FCT 2023), Lecture Notes in Computer Science, vol. 14292, pp. 421–435, Springer Cham (2023). A complete and corrected version is available at arXiv:2310.18965 (2023).