# The Computational Complexity of _Fire Emblem_ Series
and similar Tactical Role-Playing Games

Jiawei Gao The work was done when the author was a student at University of
California, San Diego. Work supported by the Simons Foundation and NSF grant
CCF-1909634.

###### Abstract

_Fire Emblem (FE)_ is a popular turn-based tactical role-playing game (TRPG)
series on the Nintendo gaming consoles. This paper studies the computational
complexity of a simplified version of FE (only floor tiles and wall tiles, the
HP and other attributes of characters are constants at most $8$, the movement
distance per character each turn is fixed to $6$ tiles), and proves that:

  1. 1.

Simplified FE is PSPACE-complete (Thus actual FE is at least as hard).

  2. 2.

Poly-round FE is NP-complete, even when the map is cycle-free, without healing
units, and the weapon durability is a small constant. Poly-round FE is to
decide whether the player can win the game in a certain number of rounds that
is polynomial to the map size. A map is called cycle-free if its corresponding
planar graph is cycle-free.

These hardness results also hold for other similar TRPG series, such as _Final
Fantasy Tactics_ , _Tactics Ogre_ and _Disgaea_.

##  1 Introduction

Many video games are proven to be NP-hard or PSPACE-complete [24, 20, 8, 15,
9, 21, 19, 18, 23, 30, 32, 31, 16, 17, 26, 28, 6]. Most of the games are
puzzle-solving or path-finding types. However, little research about the
hardness of turn-based tactical role-playing games has been conducted.

Tactical role-playing games (TRPGs) are also called “simulation role-playing
games” (SRPGs) in Japan. Nan et al.[27] calls them “war chess games”. These
games are similar to turn-based board games, where the player and the computer
take turns to move their characters in the map. The map is a grid, where
characters (which are called _units_) can move from a tile to an empty tile
each turn, and can choose to attack a nearby enemy unit or just stay in the
tile doing nothing. Each characters has some _attributes_ , or _stats_ , such
as _Hit Points(HP)_ , _Attack_ , and _Defense_. Usually the characters have
personalities and stories like most role-playing games, and are able to level
up by getting experience from battles. Well known TRPGs include _Final Fantasy
Tactics_[2], _Tactics Ogre_ , and _Disgaea_[1].

_Fire Emblem(FE)_[3, 4] is a Japanese TRPG series developed by INTELLIGENT
SYSTEMS and released on Nintendo gaming consoles and handheld gaming devices.
It has 29 years of history, with 16 titles in its main series. The feature of
FE is that all numbers involved in battles (such as attack, defense, and
damage) are relatively small (compared to most other popular TRPGs, e.g.,
_Final Fantasy Tactics_) and completely transparent to the player. The
mechanism of the game is well-studied, and the enemy units’ strategy can be
predicted by experienced players. The stages of the game are so challenging
that it encourages advanced-level players to precisely calculate the damages
dealt and taken, and also predict or even manipulate the enemy units’ moves.
Another uniqueness of the series is that in battles, the defending units can
counter attack, so in many cases it is wise no to approach the enemies rashly,
but to form a defensive formation and wait for the enemies to approach and get
defeated by counter attacks. In most other TRPGs, however, not all units can
counter attack automatically, although some units have counter attack as their
skills.

In each turn, each unit is granted to move once. A unit can move from zero to
_Mov_ tiles, where _Mov_ is an attribute of the unit indicating how far they
can move in a single turn. All distances in the game are Manhattan distance,
or in other words, computed by the L$1$-Norm: the distance from coordinate
$(0,0)$ to $(0,1)$ or $(1,0)$ is only $1$, but to coordinate $(1,1)$ would be
$2$.

If there is a hostile unit within the attack range of a unit (again by
Manhattan distance), then the unit can initiate a combat. When combat happens,
the amount of damage the defender takes from the attacker is computed by the
following formula:

$\text{damage to the defender}=\begin{cases}\text{attacker's
}\mathit{Atk}-\text{defender's }\mathit{Def}\text{, if hit}\\\ 0\text{, if
miss}\end{cases}$

After combat, the HP of the defender is decreased by the amount of the damage.
A unit dies if their HP is below zero. If the defender is still alive, they
can counter attack the attacker, using the same damage formula with their
roles switched.

Figure 1(a) shows the map of a stage. Figure 1(c) shows a gameplay screenshot
of a player unit about to move. Figure 1(c) shows a screenshot of a combat.

(a) A map of a stage

(b) A unit moves on the map. The blue tiles are positions she can move to, and
the orange tiles are positions she can attack.

(c) A unit (Franz) attacks an enemy (Soldier).

Figure 1: Screenshots of the game.

The details of the game mechanism used in this paper will be presented in
Section 3.

##  2 Main Results

The actual game play of FE series have many complicated mechanisms. Because it
involves a lot of numbers and computing, proving the hardness of a game where
the HP of units is unbounded would not be an interesting result. Therefore we
consider the simplified FE game. In the games, there are only floor tiles and
wall tiles, the HP and other attributes of characters are constants at most
$8$, the movement distance per character each turn is fixed to $6$ tiles. This
is a special case of real FE game, and can be easily adapted to most other
similar TRPGs.

Because the games studied in this paper may take too many turns than actual
gameplay, we do not consider weapon or healing staff durability, or
equivalently, let the durability of all weapons and healing staves be
infinity.

######  Definition 2.1 (Simplified FE).

Given the initial status of an FE game with infinite weapon and staff
durability, decide whether the player has a winning strategy.

This paper proves the hardness of Simplified FE:

######  Theorem 1.

Simplified FE is PSPACE-complete.

Even if it is not surprising that a two-player turn-based strategy game is
PSPACE-complete, FE is not as complicated as a typical two-player turn-based
strategy game, because the enemies’ strategy is simple, deterministic111In
real FE, the outcome after each combat is not deterministic, because the
amount of damage is randomized, affected by the rate of missing and the rate
of critical hits. But the strategy of where each enemy unit moves to and which
player unit they attacks, is always deterministic., and can be fully predicted
based on the current game configuration. Each enemy unit acts like a robot
pre-programmed with simple and straightforward commands, like “move to your
target by the shortest path, and hit the target”. For example, if an enemy
unit can reach a player unit and attack them, then the enemy unit will surely
choose to do that, even in the case where the enemy unit can make little
damage to the player unit, and would die from the player unit’s counter
attack. Another example is that, if two enemy units both attack the player’s
Lord, the Lord would be killed by the total damage and the game would be lost.
But if we place a weaker Cleric unit near to the Lord, one of the enemy units
would attack the Cleric, and the other enemy unit would attack the Lord,
leaving both the Cleric and the Lord alive.

Thus, instead of being a game of form “$\exists$ a player strategy, $\forall$
enemy strategies, $\exists$ a player strategy, $\forall$ enemy strategies …”
which can be PSPACE-complete even when the total number of turns is bounded by
a polynomial, the game is more similar to the case “$\exists$ a player
strategy, for _the_ enemy strategy, $\exists$ a player strategy, for _the_
enemy strategy, …”. Therefore, the result that FE being PSPACE-complete is not
trivial.

The reason of FE being PSPACE-complete is that it may take too many turns.
Actually, if one can make sure that a game ends in a polynomial number of
turns, then the game is in NP.

In reality, FE stages usually do not take too many turns, observing the
following facts:

(1) After each turn, the total HP of all units is decreasing fast from the
battles, even if some healing happens occasionally.

(2) In most cases, the enemy units usually move towards player units, and do
not move away. Even if some enemy units do not move if player units do not get
near them, there is little point of waiting a lot of turns before attacking.

(3) Weapons and healing staves have durability that are usually around $40$.

(4) Sometimes the game design encourages or requires players to clear each
stage as fast as possible.

So it would be interesting to ask if a stage can be finished in a certain
number of rounds.

######  Definition 2.2 (Poly-round FE).

Given the initial status of an FE game and a number $k$, where $k$ is
represented in unary, decide whether the player has a winning strategy with at
most $k$ rounds.

Poly-round FE is in NP, because a winning strategy always has a polynomial
number of turns.

Cycles in the map (e.g. a closed path surrounding a stone pillar, or a plain
with a lake in the middle) usually make stages more complicated. For example,
if there are two paths leading to the same room, we can lure enemies to one
path and go through the other. Player unit can move along a cycle for many
rounds so that the enemy chasing them will never reach them; this strategy is
useful when we need a lot of turns to heal the units, or to wait for powerful
allies in different areas of the map to come and deal with the enemies. Also,
we can let a player unit move back and forth at one side of the cycle, making
an enemy moving back and forth at the opposite side of the cycle, because the
shortest path for the enemy unit to reach the player unit keeps changing.

Thus, the game would be much simpler if we do not allow cycles in the maps.

######  Definition 2.3 (Cycle-free FE).

If a map does not have cycles when considered as a planar graph where floor
tiles are vertices and adjacent floor tiles are connected by edges, then the
stage is called _cycle-free_.

This paper shows that even if the stage is cycle-free, Poly-round FE is still
NP-complete. Because the construction in the NP-completeness proof does not
involve too many combats, we can limit the weapon durability to a small
constant. Also, in the construction, there are no healing units.

######  Theorem 2.

Poly-round FE is NP-complete, even if the map is cycle-free, the weapon
durability is a constant at least $4$, and there are no healing units.

These hardness results can also be applied to other TRPGs with similar
mechanism, although in those TRPGs, units cannot counter attack when being
attacked.

##  3 Game Mechanism

In this section we will describe our simplified FE model used in the proofs.
This simplified model fits into most real FE games, thus the hardness of these
simplified cases can demonstrate the hardness of real FE games.

Stage

The map of a stage is an $m\times n$ grid, where each tile is a square
adjacent to four other tiles in its four directions. A tile can either be
castle floor or castle wall. Units can be placed in the floor tiles, but
cannot move onto or through walls. However, ranged units (e.g., archers who
have attack range $2$) can attack through walls (imagine there are little
holes in the walls for arrows to fly through). The distance between two tiles
is defined to be their Manhattan distance.

Units

A unit is a character, which occupies one tile in the map. A unit can either
be a player unit, or an enemy unit. Some units, such as Clerics, can heal
their allies. Each unit has the following attributes:

  * •

_HP:_ the Hit Point of the unit, an integer between $1$ and $50$.

  * •

_Atk:_ the Attack of the unit, an integer between $1$ and $50$.

  * •

_Def:_ the Defense of the unit, an integer between $1$ and $50$.

  * •

_Mov:_ the maximum Manhattan distance the unit can move each turn, an integer
at most $10$.

  * •

_Range:_ the attack range of the unit. If an enemy’s distance is in the unit’s
attack range, then the unit can attack the enemy. The most common attack range
of a unit is usually either one or two.222Unlike real FE where the attack
range is affected by the weapons equipped by the units, here we assume each
unit has a fixed attack range. Healing units have healing range, where an ally
in the range can be healed by the unit.

Units of the same class always have the same _Mov_ value. The most common
_Mov_ value is $6$, which is the movability of infantry units. In the proofs,
we will always make all units have the same _Mov_ and use letter $d$ to
represent this _Mov_ value.

If a unit’s HP is zero or below, the unit is dead, and disappears immediately
from the map, and will not appear again anywhere.

Moving

In each round, the player’s turn comes first, where the player can move all
the player units; then comes the enemies’ turn, where each enemy unit moves,
controlled by the computer. The player can move the player units in any order.
In a single round, the order of the player units’ moves and the enemy units’
moves do not interleave.

In a turn, each unit can move at most one time. A unit can move to an empty
tile along a valid path within distance of their _Mov_. They can also stay in
their own tile without moving. After moving to the target tile, if an enemy
unit is in their attack range, then they can choose to attack the enemy unit.
Or they can choose to heal an ally, if there are allies in their healing
range.

Units can move through empty floor tiles, or floor tiles with other units of
their own allies. But they cannot move through wall tiles or floor tiles
occupied by hostile units.

Combat

If attacker $a$ hits defender $d$, then $d$ takes damage equal to ($a$’s _Atk_
$-d$’s _Def_). $d$’s HP is decreased by the damage value. If $d$ is still
alive (HP $>0$) and $a$ is in $d$’s attack range, then $d$ immediately counter
attacks $a$. $a$ takes damage equal to ($d$’s _Atk_ $-a$’s _Def_). Afterwards,
$a$’s HP is decreased by the damage value.

In the hardness proofs, we only consider the cases where attacks always hit
and never miss.

Objective

The most common objective of FE stages is to “seize the throne”. There is a
unique tile in the map representing a throne, and there is a main character
among the player units called the Lord. The goal of the stage is to move the
Lord to the throne tile (if it is not occupied by enemies, of course.) If the
Lord is dead, then the player loses the game immediately.

In real FE stages, there are also other objectives than seizing the throne,
such as rout the enemy, defeat the enemy leader, survive for a certain number
of turns or escape from the exit. This paper will not use these objectives in
the hardness proofs.

Enemy strategies

In FE, there are two types of enemy units:

  * •

_Impatient enemy:_ If there are player units in their move-and-attack range
(i.e., if the enemy moves, then the player unit is in the enemy’s range), then
they will choose the player unit with the lowest defense, move to the unit by
the shortest path and attack the unit. Otherwise, if there are player units in
the same connected component of the map, then they will choose the player unit
in the same connected component with the lowest defense as their target, and
moves to the target by the shortest path (even if the path may be blocked by
another player or enemy unit).

  * •

_Patient enemy:_ If there are player units in their move-and-attack range,
then they will choose the player unit with lowest defense, move to the unit by
the shortest path and attack the unit. Otherwise, they do not move at all.
Once the patient enemy takes part in any combat, they will turn into an
impatient enemy and will not turn back to patient ones ever again.

The order of enemy units’ moves is fixed, by the implicit order that enemy
units are created on the map. In the hardness proofs we will make the stages
order-invariant. If there are multiple targets for an enemy, they will break
ties by the order that the player units are created. If there are multiple
shortest paths, they will break ties by selecting a path that moves
horizontally as far as possible and then moves vertically. In the hardness
proofs we will avoid creating multiple targets or multiple paths for enemies.

In this paper, for simplicity we consider the game setting where there are no
critical hits, dodged or ineffective attacks, personal skills, special effect
weapons, terrain effects, support effects, item exchange, and weapon
triangles, even if these features appear in many FE titles. Also we assume
characters will not level up in the stage, thus the values of attributes of a
unit will never change. For readers who are FE players, consider the case
where all unrelated attributes like _speed_ , _skill_ , _luck_ are zero, all
units use the same type of weapon, and the experience gained by combats is too
small to level up units. The proofs will avoid the possibility for terrain
effects, support effects and item exchange.

##  4 The NP-hardness of Poly-round Cycle-free FE

This section proves Theorem 2. We reduce from Rectilinear Monotone 3-Bounded
3-SAT 333[11] and [29] used the term ”Planar Monotone 3-Bounded 3SAT” to
define a different problem, where the planar graph does not require positive
clauses and negative clauses to be placed on opposite sides. So here we use
the word ”Rectilinear” as in [12], even if [12] does not use ”Rectilinear” as
part of the problem name.. It is a 3-SAT problem satisfying the following
conditions:

  * •

In each clause, either all literals are positive, or all literals are
negative.

  * •

Each variables appears as a positive literal in at most three clauses, and as
a negative literal in at most three clauses.

  * •

If we treat each variable and each clause as a vertex, and connect a pair of
variable and clause by an edge if the variable appears in the clause, then the
resulting graph is a planar graph.

  * •

Moreover, in the planar graph, we can place all variable vertices in a line,
put all clauses with positive literals on one side, and put the clauses with
negative literals on the other side.

To show Rectilinear Monotone 3-Bounded 3-SAT is NP-complete, we reduce from
Planar Monotone 3-SAT [12], which is NP-complete. This problem is similar to
Rectilinear Monotone 3-Bounded 3-SAT, but the number of clauses each variable
appears in is unbounded. To make each variable appear in at most three
positive clauses and three negative clauses, we make the following
modification on each variable:

For variable $x$ that appears in $k$ clauses, we create new variables
$x_{1}^{T},x_{1}^{F},\dots,x_{k}^{T},x_{k}^{F}$, and connect them by clauses
as shown in Figure 2. In this way, $x_{i}^{T}$ and $x_{i}^{F}$ must have
different truth values, and $x_{i}^{F}$ and $x_{i+1}^{T}$ must have different
truth values. So either all $x_{i}^{T}$ are true and all $x_{i}^{F}$ are
false, or all $x_{i}^{T}$ are false and all $x_{i}^{F}$ are true. Because all
$x_{i}^{T}$ have the same truth value, we will let these variables substitute
all the appearances of variable $x$ in clauses. If $x$ is in some positive
clause, we connect it to the clause on one side. If it is in some negative
clause, we connect it to the clause on the other side.

Figure 2: Reduction from Planar Monotone 3-SAT to Rectilinear Monotone
3-Bounded 3-SAT.

Next we will reduce Rectilinear Monotone 3-Bounded 3-SAT to Poly-round Cycle-
free FE. For each variable, we create a Player Variable Unit. For each clause,
we create a Player Clause Unit. And we create another player unit which is the
Lord, whose objective is to seize the throne. For each literal we create an
Enemy Literal Unit. For each variable, we create $2d-1$ Enemy Sniper 444A
Sniper is a promoted Archer. This paper calls them Snipers instead of Archers
because they are so dangerous that can easily defeat a player unit. Units,
where $d$ is the _Mov_ of the units. In the figures, $d$ is shown to be $6$.
Table 1 shows the attributes of all units in the construction.

Unit | HP | Atk | Def | Range
---|---|---|---|---
Player Variable Unit | 4 | 3 | 1 | 2
Player Clause Unit | 3 | 2 | 1 | 2
Player Lord | 1 | 2 | 1 | 1
Enemy Literal Unit | 2 | 2 | 1 | 2
Enemy Sniper Unit | 2 | 5 | 2 | 2
Table 1: Attributes of all units in the NP-hardness proof. All units has Mov =
6.

Variable gadget

Figure 3 shows a variable gadget. In the center of the $i$-th variable gadget
we put a Player Variable Unit $V_{i}$. $V_{i}$ is located in a vertical long
room of distance $2d+1$. Moving upwards corresponds to setting variable
$v_{i}$ to true, while moving downwards corresponds to setting it to false.

Figure 3: Variable gadget. The blue carpet tiles represent the floor. The
lighter and darker blue tiles are the same, where the colors are aesthetic
design to show the tiles clearly, and do not have particular meaning. The
brick tiles represent castle walls.

Above $V_{i}$, there are at most three patient enemy units
$E_{1},E_{2},E_{3}$. Each enemy unit corresponds to a positive literal of the
variable $v_{i}$ in some clause. Similarly, below $V_{i}$, there are also at
most three enemy units $E_{1}^{\prime},E_{2}^{\prime},E_{3}^{\prime}$, each
corresponding to a negative literal of $v_{i}$ in some clause.

If $V_{i}$ moves up to the tile labeled $T$, then all three enemy units above
will be alert because $V_{i}$ is in their range, because their distance to the
tile labeled $a$ is $d$. They will move down to position $a$ to attack
$V_{i}$. Each enemy unit makes damage $1$ to $V_{i}$, so $V_{i}$ will lost at
most $3$ HP. In the counter attacks, $V_{i}$ makes damage $2$ to each of the
enemy units, so the three enemy units will not survive $V_{i}$’s counter
attacks. Thus, if $V_{i}$ moves up to position $T$, the above three enemy
units will disappear from the map; similarly, if $V_{i}$ moves down to the
tile labeled by $F$, the three enemy units below will disappear.

The room labeled “sniper room” to the right of $V_{i}$’s room has length
$2d-1$ and is filled with Enemy Sniper Units of range $2$, with _Atk_ so high
that one single shot will take $V_{i}$’s life, and _HP_ \+ _Def_ high enough
so that they cannot be defeated by $V_{i}$ by one shot. Thus, $V_{i}$ must
move to either position $T$ or position $F$ in the first turn. Once $V_{i}$
has chosen to move up to position $T$ in the first turn, then $V_{i}$ cannot
move down to position $F$, and vice versa.

Above the three enemy units there are three paths. The three paths wind their
way around the three enemy units, with the nearest distance to the enemy units
being $2$. The nearest tiles are labeled by $b$, $c$ and $d$. These paths
correspond to the clauses the variable $v_{i}$ is contained in. Units in
clause gadgets will go along these paths to encounter the enemy units.

Clause gadget

We consider the clauses with exactly three literals. A gadget for clause
$c_{j}$ is a long path which goes around the three enemy units corresponding
to its three literals appearing in clause $c_{j}$. The paths for clauses with
all positive literals are placed above the variable gadgets, and the clauses
with all negative literals are below them. A Player Clause Unit $C_{j}$ needs
go along the path to clear all the remaining Enemy Literal Units in their own
clause, that are not cleared by any Player Variable Units. The path itself is
a connected component, so $C_{j}$ cannot move to any variable gadget or other
clause gadgets. Because the variable-clause graph corresponding to the CNF
formula is a planar graph, the clause gadgets can be embedded in the grid map
without intersecting each other.

If $C_{j}$ is at location $b$ (or $c,d$), then $C_{j}$ a chance to attack
enemy unit $E_{1}$ (or $E_{2},E_{3}$ respectively). The battle between $C_{j}$
and an enemy takes two turns:

  1. 1.

Enemies’ turn: Enemy unit damages $1$ HP to $C_{j}$, $C_{j}$ damages $1$ HP to
enemy unit.

  2. 2.

Player’s turn: $C_{j}$ damages $1$ HP to enemy unit. Enemy unit is dead and
cannot counter attack.

This is the best strategy for $C_{j}$. For otherwise if in a turn, $C_{j}$
attacks first, then it will be damaged by $1$ HP from the counter attack. Then
in the enemies’ turn, the enemy unit will kill $C_{j}$.

Thus, $C_{j}$ loses at least $1$ HP when taking out an enemy unit. $C_{j}$ has
$3$ HP in the beginning, thus if there are three enemy units remaining in the
clause (which means all three literals are false), then $C_{j}$ not able to
defeat all of them. Otherwise, $C_{j}$ can clear all enemy units corresponding
to their clause.

For clauses with fewer than $3$ literals, we modify the corresponding $HP$ of
$C_{j}$ to be the number of literals in the clause.

Main Road

The player Lord unit enters the castle from bottom left gate, and goes along
the main road inside the castle which leads to the throne. The main road
traverses through the negative sides of all variable gadgets, and then through
the positive sides of all variable gadgets, and finally reaches the throne.
The Lord is very weak: she has attack range only one, and cannot survive any
attack from an enemy unit. The lord can only pass through all variable gadgets
if all Enemy Literal Units are cleared.

In Figure 3, suppose the Lord is moving through the positive part of the
variable gadget, from the right of the map to the left of the map. The road
goes through the trident shaped room where the enemy units $E_{1},E_{2}$ and
$E_{3}$ are located. If the Lord moves to a tile between the tiles labeled by
$f$ and the tile labeled by $e$, including $f$ and $e$, then she will be
attacked by all three enemy units $E_{1},E_{2},E_{3}$. Also the Lord cannot
avoid ending a turn in tiles between $e$ and $f$, because the distance from
$e$ to $f$ is greater than $d-1$. Thus, the Lord can only pass when all three
enemy units have been cleared: which means either they have been defeated by
the variable unit (the variables is set to true so that the literals are true)
or they have been defeated by the clause unit (the clause value is true even
if these literals are false).

Figure 4 shows a simplified overview of the whole map. In this example, the
3-CNF formula is

$\varphi=(v_{1}\vee v_{2}\vee v_{4})\wedge(v_{4}\vee v_{6}\vee
v_{7})\wedge(v_{1}\vee v_{4}\vee v_{7})\wedge\\\ (\neg v_{1}\vee\neg
v_{6}\vee\neg v_{7})\wedge(\neg v_{1}\vee\neg v_{2}\vee\neg v_{6})\wedge(\neg
v_{2}\vee\neg v_{3}\vee\neg v_{5})\wedge(\neg v_{3}\vee\neg v_{4}\vee\neg
v_{5})$

Figure 4: Overview of the map showing simplified variable gadgets, clause
gadgets and the main road. The lighter and darker blue tiles are the same, and
the colors do not have particular meaning.

If there is a satisfying assignment to the CNF-formula, then in each clause at
least one Enemy Literal Unit is cleared by the move of a Player Variable Unit,
then the Player Clause Unit can clear all the remaining Enemy Literal Units,
and thus Lord can always reach the throne. In the other direction, if the Lord
can reach the throne, then it means all Enemy Literal Units are cleared, so
each clause has at least a true literal, thus the Player Variable Units’ moves
gives a satisfying assignment of the CNF formula. Thus Theorem 2 follows.

Moving all the $V_{i}$ takes one round. After the first round, all $C_{j}$
moves in their paths in one direction, and the Lord moves along the main road
in one direction. Thus the total number of rounds taken to win is bounded by
the total number of tiles of the map.

In the construction, the total number of attacks and counter attacks by each
unit is at most $4$ times, so it works even when the weapon durability in the
game is a fixed constant greater than or equal to $4$.

For other TRPGs where units cannot make counter attacks, we can adapt our
construction for these games. The new table of attributes is Table 2, where
modified values are shown in bold font.

Unit | HP | Atk | Def | Range
---|---|---|---|---
Player Variable Unit | 7 | 3 | 1 | 2
Player Clause Unit | 3 | 2 | 1 | 2
Player Lord | 1 | 2 | 1 | 1
Enemy Literal Unit | 2 | 2 | 1 | 2
Enemy Sniper Unit | 2 | 8 | 2 | 2
Table 2: Attributes of all units in the NP-hardness proof, in TRPGs without
counter attack.

Variable Gadget: When $V_{i}$ moves to position $T$ (or $F$), they will be
attacked at most three times by $E_{1},E_{2},E_{3}$ (or
$E_{1}^{\prime},E_{2}^{\prime},E_{3}^{\prime}$), losing at most $3$ HP. In the
next round, $V_{i}$ kills one enemy unit, and takes at most $2$ damage. In the
third round, $V_{i}$ kills another enemy unit, taking at most $1$ damage from
the last enemy unit. Finally, $V_{i}$ kills the last enemy unit. So $V_{i}$
needs to have at least $7$ HP in the beginning. The Enemy Snipers need to have
_Atk_ at least $8$ to be able to kill $V_{i}$ by a single shot.

Clause Gadget: To defeat an Enemy Literal Unit, $C_{j}$ must lose at least one
$1$ HP. The way for $C_{j}$ to defeat an Enemy Literal Unit $E$ losing only
$1$ HP is as follows:

  1. 1.

Player’s turn: $C_{j}$ damages $1$ HP to enemy unit.

  2. 2.

Enemies’ turn: Enemy unit damages $1$ HP to $C_{j}$.

  3. 3.

Player’s turn: $C_{j}$ damages $1$ HP to enemy unit. Enemy unit is dead.

In the TRPGs where the goal of a stage is to defeat all enemies or defeat the
enemy leader, we could replace the throne by a patient enemy leader with _Atk_
, _HP_ and _Def_ being one, so that they can be defeated by the Lord.

Thus, this reduction works for these TRPGs, as long as they support distance
$2$ attacks and patient enemies.

##  5 Simplified FE is PSPACE-complete

This section proves Theorem 1: Simplified FE is PSPACE-complete. We use the
technique introduced in [30] and later used in [31, 7, 17], which is called
the “open-close door” framework:

_In a game whose goal is to move a player-controlled avatar from the starting
location to an ending location along a path, if we can create _open-close door
gadgets_ and _crossover gadgets_ , then there is a reduction from True
Quantified Boolean Formula (TQBF) to the game._

An _open-close door gadget_ has a door with three states, an initial state
(which may be the same as the close state), an open state and a close state.

There are three distinct paths going through the gadget: a traverse path, an
open path, and a close path.

  * •

The avatar can go through the traverse path in any direction if and only if
the door is in the open state.

  * •

If the avatar goes through the open path, they may push an “open” button to
let the door open.

  * •

If the avatar goes through the close path, they are forced to push a “close”
button to let the door close.

The door should be able to be opened, closed, and travered through for an
arbitrary number of times.

Though not explicitly stated in the papers, their construction actually has
the following fact:

######  Claim 3.

This framework works even if the paths through the doors are not strictly one
directional, allowing the avatar to traverse the paths reversely, and

  * •

When the close path is traversed reversely, the door is forced to open;

  * •

When the open path is traversed reversely, the door is forced to close;

  * •

When open path is traversed in the correct direction, the door is forced to
open.

  * •

When the door is already open and the open path is traversed again in the
correct direction, the door remains open;

  * •

When the door is already closed and the close path is traversed again in the
correct direction, the door remains closed.

The last three points of the above claim can be observed from the quantifier
gadgets and clause gadgets constructed in [30]. The first two points will be
proved in Section 5.1.

A _crossover gadget_ is a gadget to enforce any two paths A and B cross each
other without leakage. That is, an avatar on A and should continue on path A
and should not end up on path B, and vice versa.

We construct a FE stage which supports the open-close door gadgets and the
crossover gadgets. In our construction, the player has one main unit, which we
call the Lord. We will also create a lot of healing units, who can heal at
least $2$ HP to the Lord each time. On the enemy side, there is a Dragon,
corresponding to each door gadget there is a Door Gadget Unit, and also there
are a lot of Sniper Units that will be useful in the crossover gadgets. Table
3 shows the attributes of all units in the construction. All units has _Mov_
value $d=6$.

Unit | HP | Atk | Def | Range
---|---|---|---|---
Player Lord | 3 | 1 | 1 | 2
Enemy Dragon | 5 | 5 | 5 | 1
Enemy Door Gadget Unit | 2 | 2 | 2 | 2
Enemy Sniper | 5 | 5 | 5 | 2
Table 3: Attributes of all units in the PSPACE-completeness proof.

In the construction, our Lord has attack range $2$. Her goal is to travel from
her starting position to the throne. There is a narrow path and the Lord has
to run at full speed without stopping. A dangerous dragon $D$, who is an
impatient enemy with attack range $1$, is placed behind her initially at
distance $2$. The Lord must move distance $d$ along the path each turn, for
otherwise $D$ will reach her and kill her. Every time the player’s turn ends,
the dragon moves to a tile behind the Lord, keeping distance $2$. Thus, the
Lord is forced to end her turns in the tiles of distance $i$ along the path
where $i\mbox{ mod }d=0$. We call these tiles the _safe tiles_.

Door gadget

Figure 5: Door gadget. The red carpet tiles are floor tiles, and the stone
tiles are castle walls. The tiles with yellow rim are safe tiles.

As shown in Figure 5, in the middle of the door gadget there is a horizontal
room of length $d+2$. In the room at the tile labeled by $E$ we place an Enemy
Door Gadget Unit, who is an Archer. He has attack range $2$, and can deal $1$
damage to player Lord. On the other hand, the player Lord cannot damage him at
all. If the Lord goes along the traverse path, her safe tile will be position
$c$. Then if the enemy Archer is at position $E$, he will move to position
$B$, so that the player gets one damage from the Archer.

To open the door, the Lord goes through the path below the room, from right to
left. Positions $b$ and $a$ are safe tiles. When she stays on position $b$, no
matter where the enemy unit is currently located in the room, the enemy unit
can always shoot her from position $E$. When she stays on position $a$, the
enemy unit moves to position $A$ and shoots her again. Then the Lord moves
away, and the enemy unit stays at position $A$. The Lord has lost $2$ HP.
After opening the door, we will place a healing unit on the Lord’s path to
heal her back to $3$ HP.

Before going through the traverse path, the Lord should have been already
damaged by $2$ HP, and has only $1$ HP left when she goes along the path to
the right of the room. So if the enemy unit is not on position $A$, then he
can shoot the Lord by moving to position $B$; otherwise he will not hurt the
Lord because the Lord is out of range. If the Lord is shot by the enemy unit,
she dies and the game is over. After traversing pass the enemy unit room, we
place a healing unit on the Lord’s path to heal her back to $3$ HP.

To close the door, the Lord goes along the close path above the room from left
to right, which is symmetric to the open path. When she stands on position
$b^{\prime}$, the enemy unit inside the room is lured back to position $E$,
and will stay on position $E$ afterwards. After closing the door, we place a
healing unit on the Lord’s path to heal her back to $3$ HP.

Crossover gadget

When two paths cross each other, we always let one path be horizontal and the
other be vertical. Relative to the whole map, each tile has a horizontal
coordinate and a vertical coordinate. We arrange the crossings carefully to
make sure that each tile at the crossing of two paths has both vertical and
horizontal coordinates modulo $d$ equal $0$. Around the crossing tile, on the
horizontal path, the safe tiles’ distance from the crossing modulo $d$ equals
$s_{1}$, while on the vertical path, the safe tiles’ distance from the
crossing modulo $d$ equals $s_{2}$, satisfying:

  * •

$s_{1}\neq s_{2}$, and

  * •

$s_{1}\neq d-s_{2}$, and

  * •

$d-s_{1}\neq s_{2}$, and

  * •

$d-s_{1}\neq d-s_{2}$.

Also, before and after each crossing, there are straight paths long enough to
hide powerful Snipers behind the walls to shoot the Lord if she is not in a
safe tile. So the Lord can only stay in the safe tiles. If the Lord was moving
right, but at the crossing she chose to move down (or up), then because she
must stay at the tiles of distance $i\cdot d+s_{1}$ for integer $i$ from the
crossing, but the safe tiles are of distance $i\cdot d+s_{2}$ (or $i\cdot
d-s_{2}$) for integer $i$ from the crossing, so the Lord will be shot by
Snipers behind the walls. Similarly, if the Lord was moving left, down or up,
she cannot turn into any other direction at the crossing.

Figure 6 shows an crossover gadget. Here $d=6$, $s_{1}=1$ and $s_{2}=3$. When
the Lord goes from left to right, the first tile after the crossing is the
safe tile. When she goes top-down, the third tile after the crossing is the
safe tile. The rooms in the walls are sniper rooms, where the Enemy Snipers
Units would shoot the Lord if she does not stay on the safe tiles.

Figure 6: Crossover gadget. The tiles with yellow rim are safe tiles.

(a) Turning from right to down/from up to left.

(b) Turning from left to down/from up to right.

(c) Turning from down to right/from left to up.

(d) Turning from down to left/from right to up.

Figure 7: Turning gadgets. The tiles with yellow rim are safe tiles.

Turning gadget

The turning gadgets are question mark shaped curves that shifts the positions
of safe tiles between horizontal paths and vertical paths, so that the
coordinates of the safe tiles satisfy the condition described in the crossover
gadget. Figure 7 shows the turning gadgets of all directions.

Healing and damaging units used in door gadgets

A Healing Unit is a player Cleric unit in a single-tile room, using the Psysic
Staff whose healing range is from $2$ to $10$. The distance from the room to
the nearest tile, which is a safe tile, is $2$. So when the Lord moves to the
safe tile, the Cleric can heal the Lord to $3$ HP.

A Damaging Unit is a enemy unit of attack range $2$ in a similar single-tile
room. He can deal $2$ damage to the Lord. We also give him _Def_ no less than
the Lord’s _Atk_ so that he won’t take any damage from the Lord.

Figure 8 shows the single-tile room and the main path.

Figure 8: Healing and damaging unit. When the Lord stays on the yellow rim
tile, she gets healed or damaged by the unit in the room.

In this way, we have created open-close door gadgets and crossover gadgets.
This means Simplified FE can be reduced from TQBF. Therefore Simplified FE is
PSPACE-complete.

This construction can be applied to other TRPGs, as long as they support
distance $2$ attacks and distance $2$ healing, and have impatient enemy units
that takes the initiative to chase the player unit down.

###  5.1 Constructing one-way paths using two-way doors

This section explains the first two points in Claim 3, whose conditions are
satisfied by our construction of the open-close door gadgets.

Viglietta’s reduction from TQBF [30] uses open-close door gadgets to construct
clause gadgets and quantifier gadgets for TQBF. In those gadgets, there are
one-way paths containing sequences of open paths, close paths and traverse
paths of different door gadgets. The open paths and close paths are supposed
to be one-way. In our construction, we do not have one-way paths. In the door
gadgets we have created, the open paths and close paths can be traversed in
both directions. By going through an open path reversely, the door will be
closed. By going through a close path reversely, the door will be open. It is
like a “switch” that can be turned on and off by pushing the bar to the two
sides.

To ensure a path in a quantifier or clause gadgets to be one-directional, we
add the following structure in the path, as shown in Figure 9. The traverse
path is guarded by two switches on both sides. When going from left to right,
the door is open and can be traversed. When going from right to left, the door
is closed and cannot be traversed.

Figure 9: Using two-direction doors to create single-direction paths.

##  6 Open Problems

Monotone FE

Consider Simplified FE without any healing units. The HP of each unit is
always non-increasing. Is this game still PSPACE-complete, or is it easier in
computational complexity?

Range-$1$ FE

In the proofs, we constructed a lot of units with attack range or healing
range $2$. This is convenient because we can separate the map into disjoint
parts, so that units cannot enter the paths of other units. Thus, a
interesting question would be: can we prove the game is PSPACE-complete even
when each unit has either attack range $1$ or healing range $1$?

## Acknowledgments

Last year my advisor Russell Impagliazzo gave an Algorithms course, and I was
one of the TAs. The final project of the course was to choose a game and study
its algorithms/complexity. I have graded a lot of students’ submissions, which
are very interesting and insightful. That gives the motivation to study the
complexity of Fire Emblem, my favorite video game series.

I would like to thank my friend Shiwei Weng, who provided some helpful
comments on a previous draft. I am also thankful to the awesome map drawing
tool from Serenes Forest, uploaded by user BwdYeti [5]. Finally I would like
to thank the game developers of INTELLIGENT SYSTEMS, for making this wonderful
series.

## References

  * [1] Disgaea Portal.  http://disgaea.us/.  [Online; accessed September 2019].
  * [2] Final Fantasy Tactics.  http://dlgames.square-enix.com/fft/en/.  [Online; accessed September 2019].
  * [3] Fire Emblem Three Houses.  https://fireemblem.nintendo.com/three-houses/.  [Online; accessed September 2019].
  * [4] Japanese Official Site of FE Series.  https://www.nintendo.co.jp/fe/index.html.  [Online; accessed September 2019].
  * [5] FE Map Creator (also generates random maps).  https://forums.serenesforest.net/index.php?/topic/50953-fe-map-creator-also-generates-random-maps/, 2014\.  [Online; accessed September 2019].
  * [6] Matteo Almanza, Stefano Leucci, and Alessandro Panconesi.  Trainyard is np-hard.  Theoretical Computer Science, 748:66–76, 2018.
  * [7] Greg Aloupis, Erik D Demaine, Alan Guo, and Giovanni Viglietta.  Classic nintendo games are (computationally) hard.  Theoretical Computer Science, 586:135–160, 2015.
  * [8] Therese C Biedl, Erik D Demaine, Martin L Demaine, Rudolf Fleischer, Lars Jacobsen, and J Ian Munro.  The complexity of clickomania.  More games of no chance, 42:389–404, 2002.
  * [9] Graham Cormode.  The hardness of the lemmings game, or oh no, more NP-completeness proofs.  In Proceedings of Third International Conference on Fun with Algorithms, pages 65–76, 2004.
  * [10] Diogo M Costa.  Computational complexity of games and puzzles.  arXiv preprint arXiv:1807.04724, 2018.
  * [11] Andreas Darmann, Janosch Döcker, and Britta Dorn.  On planar variants of the monotone satisfiability problem with bounded variable appearances.  arXiv preprint arXiv:1604.05588, 2016.
  * [12] Mark de Berg and Amirali Khosravi.  Optimal binary space partitions in the plane.  In International Computing and Combinatorics Conference, pages 216–225. Springer, 2010.
  * [13] Ronald de Haan and Petra Wolf.  Restricted power-computational complexity results for strategic defense games.  In 9th International Conference on Fun with Algorithms (FUN 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [14] Erik D Demaine.  Playing games with algorithms: Algorithmic combinatorial game theory.  In International Symposium on Mathematical Foundations of Computer Science, pages 18–33. Springer, 2001.
  * [15] Erik D Demaine, Susan Hohenberger, and David Liben-Nowell.  Tetris is hard, even to approximate.  In International Computing and Combinatorics Conference, pages 351–363. Springer, 2003.
  * [16] Erik D Demaine, Joshua Lockhart, and Jayson Lynch.  The computational complexity of portal and other 3d video games.  arXiv preprint arXiv:1611.10319, 2016.
  * [17] Erik D Demaine, Giovanni Viglietta, and Aaron Williams.  Super mario bros. is harder/easier than we thought.  2016\.
  * [18] Rudolf Fleischer and Gerhard J Woeginger.  An algorithmic analysis of the honey-bee game.  Theoretical Computer Science, 452:75–87, 2012.
  * [19] Michal Forišek.  Computational complexity of two-dimensional platform games.  In International Conference on Fun with Algorithms, pages 214–227. Springer, 2010.
  * [20] Erich Friedman.  Pushing blocks in gravity is NP-hard.  Unpublished manuscript, March, 2002.
  * [21] Robert A Hearn and Erik D Demaine.  PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.  Theoretical Computer Science, 343(1-2):72–96, 2005.
  * [22] Robert A Hearn and Erik D Demaine.  Games, puzzles, and computation.  AK Peters/CRC Press, 2009.
  * [23] Nathaniel Johnston.  The complexity of the puzzles of final fantasy xiii-2.  arXiv preprint arXiv:1203.1633, 2012.
  * [24] Richard Kaye.  Minesweeper is NP-complete.  The Mathematical Intelligencer, 22(2):9–15, 2000.
  * [25] Graham Kendall, Andrew Parkes, and Kristian Spoerer.  A survey of NP-complete puzzles.  ICGA Journal, 31(1):13–34, 2008.
  * [26] Neeldhara Misra.  Two dots is np-complete.  In 8th International Conference on Fun with Algorithms (FUN 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [27] Hai Nan, Bin Fang, Guixin Wang, Weibin Yang, Emily Sarah Carruthers, and Yi Liu.  Turn-based war chess model and its search algorithm per turn.  International Journal of Computer Games Technology, 2016:1, 2016\.
  * [28] Matthew Stephenson, Jochen Renz, and Xiaoyu Ge.  The computational complexity of angry birds and similar physics-simulation games.  In Thirteenth Artificial Intelligence and Interactive Digital Entertainment Conference, 2017.
  * [29] Simon Tippenhauer and Wolfgang Muzler.  On planar 3-sat and its variants.  Fachbereich Mathematik und Informatik der Freien Universitat Berlin, 2016.
  * [30] Giovanni Viglietta.  Gaming is a hard job, but someone has to do it!  Theory of Computing Systems, 54(4):595–621, 2014.
  * [31] Giovanni Viglietta.  Lemmings is PSPACE-complete.  Theoretical Computer Science, 586:120–134, 2015.
  * [32] Toby Walsh.  Candy crush is np-hard.  arXiv preprint arXiv:1403.1911, 2014.


# Sequences with increasing subsequence

Łukasz Mazurkiewicz<EMAIL_ADDRESS>and  Szymon Żeberski
<EMAIL_ADDRESS>Łukasz Mazurkiewicz, Szymon Żeberski, Faculty of
Pure and Applied Mathematics, Wrocław University of Science and Technology,
50-370 Wrocław, Poland

###### Abstract.

We study analytic and Borel subsets defined similarily to the old example of
analytic complete set given by Luzin. Luzin’s example, which is essentially a
subset of the Baire space, is based on the natural partial order on naturals,
i.e. division. It consists of sequences which contain increasing subsequence
in given order.

We consider a variety of sets defined in a similar way. Some of them occurs to
be Borel subsets of the Baire space, while others are analytic complete, hence
not Borel.

In particular, we show that an analogon of Luzin example based on the natural
linear order on rationals is analytic complete. We also characterise all
countable linear orders having such property.

The work has been partially financed by grant 8211204601, MPK: 9130730000 from
the Faculty of Pure and Applied Mathematics, Wrocław University of Science and
Technology.
AMS Classification: Primary: 03E75, 28A05, 54H05; Secondary: 03E17
Keywords: analytic set, Borel set, Polish space, analytic-complete set, Borel
reduction, partial order, linear order

##  1\. Introduction

We will use standard set theoretic notions (mostly following [3] and [1]). In
particular, $\omega$ is the first infinite cardinal, i.e. the set of all
natural numbers, $\mathbb{N}=\omega\setminus\\{0\\}$ is the set of all
positive natural numbers, $\operatorname{\omega^{<\omega}}$ and
$\operatorname{2^{<\omega}}2$ are sets of finite sequences of elements of
$\omega$ and $\\{0,1\\}$, respectively. For this part assume that
$\mathcal{X}$ and $\mathcal{Y}$ are Polish spaces, i.e. separable completely
metrizable topological spaces. Classical examples are the real line
$\mathbb{R}$, the Baire space $\omega^{\omega}$, $\mathbb{N}^{\omega}$, the
Cantor space $2^{\omega}$.

######  Definition 1.

We say that $A\subseteq\mathcal{X}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete if $A$ is analytic and for
every Polish space $\mathcal{Y}$ and every analytic $B\subseteq\mathcal{Y}$
there is a Borel map $f:\mathcal{Y}\rightarrow\mathcal{X}$ such that
$f^{-1}(A)=B$.

######  Definition 2.

Let $A\subseteq\mathcal{X}$, $B\subseteq\mathcal{Y}$. We say that $B$ is Borel
reducible to $A$ if there is a Borel map $f:\mathcal{Y}\rightarrow\mathcal{X}$
satisfying $f^{-1}(A)=B$.

######  Fact 1.1.

If an analytic set $B$ is Borel reducible to $A$ and $B$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete, then $A$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

Note that existence of analytic non-Borel sets and closure of Borel sets under
Borel maps implies that all $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete
sets are not Borel. Moreover, in order to apply 1.1, we need an example of
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete set. Such an example can be
found among trees over $\omega$.

######  Definition 3.

A set $T\subseteq\operatorname{\omega^{<\omega}}$ is a tree over $\omega$ if

$\left(\forall\sigma\in\operatorname{\omega^{<\omega}}\right)\left(\forall\tau\in\operatorname{\omega^{<\omega}}\right)\left(\sigma\in
T\land\tau\subseteq\sigma\implies\tau\in T\right).$

Set of all trees over $\omega$ will be denoted by
$\operatorname{Tr_{\omega}}$. A body of a tree $T$ is a set

$[T]=\left\\{\sigma\in\operatorname{\omega^{\omega}}:\left(\forall
n\in\omega\right)\left(\sigma\upharpoonright n\in T\right)\right\\}.$

Using above definition set $\operatorname{Tr_{\omega}}$ can be seen as a
$G_{\delta}$ subset of $P(\operatorname{\omega^{<\omega}})$. Therefore,
$\operatorname{Tr_{\omega}}$ is a Polish space. By
$\operatorname{IF_{\omega}}$ let us denote the collection of all ill-founded
trees over $\omega$, i.e. all trees with non-empty body. It occurs that
$\operatorname{IF_{\omega}}$ is an example of
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete set we were looking for (see
e.g. [3, Example 4.2.1]).

Given an analytic set, proving its analytic completeness is a fundamental way
of showing that it is not Borel. As shown in [6],
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete (or, in this case, rather
$\operatorname{\mathbf{\Pi}_{1}^{1}}$-complete) sets can be used in not
necessarily set theoretic context. In the paper, authors investigate
properties of regular languages of thin trees. In particular, they are
interested in descriptive properties of such languages. One of their result is
that regular language, which does not fulfil some definability condition (so
called not WMSO-definable language), is
$\operatorname{\mathbf{\Pi}_{1}^{1}}$-complete.

Naturally, $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete sets can be
useful in more set theory-related research. Like in [5], where class of all
Banach spaces isomorphic to $c_{0}$ is considered. The main result of the work
states that this class is a complete analytic set (with respect to Effros
Borel structure), so it can not be Borel.

In [4], a class of coloring problems induced by actions of countable group on
Polish spaces is studied. It is shown, that the set of such coloring problems,
which additionally have Baire measurable solution for a particular free action
$\alpha$, is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete (when $\alpha$
is not trivial).

In this paper we would like to examine descriptive complexity of sequences
with increasing subsequence, seen as a subset of
$\operatorname{\omega^{\omega}}$ (or other space homeomorphic to it). The
motivation comes from classical example of Lusin (which can be found in [2,
27.2]):

######  Theorem 1.2 (Lusin).

Let $\mid$ be a division of positive natural numbers $\mathbb{N}$. Set

$L=\\{y\in\mathbb{N}^{\omega}:(\exists k_{0}<k_{1}<\ldots)(\forall
i\in\omega)(y(k_{i})\mid y(k_{i+1}))\\}.$

$L$ is a $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete subset of
$\mathbb{N}^{\omega}$.

We want to study the descriptive complexity of sets defined in a similar
fashion. Assume that $X$ is countable set and $R$ is a relation on $X$. Define

$L_{(X,R)}=\\{y\in X^{\omega}:(\exists k_{0}<k_{1}<\ldots)(\forall
i\in\omega)(y(k_{i})Ry(k_{i+1}))\\}.$

In the next section we will provide some basic facts and discuss the
complexity of $L_{(X,R)}$ for various examples of $(X,R)$. We will focus
mainly on the case of posets, i.e sets equipped with a relation which is
reflexive, symmetric and transitive. Later we will consider linear orders and
give a characterization of those for which the set $L_{(X,R)}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

##  2\. Basic examples

First we shall observe that projective class of $L_{(X,R)}$ can not exceed
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$.

######  Fact 2.1.

Assume that $R\subseteq X\times X$ and $|R|\leq\aleph_{0}$. Then the set
$L_{(X,R)}$ is analytic.

###### Proof.

Let us define

$B_{(X,R)}=\\{(k,y)\in\operatorname{\omega^{\omega}}\times X^{\omega}:(\forall
i\in\omega)(k_{i}<k_{i+1}\land y(k_{i})Ry(k_{i+1}))\\}.$

Notice that $B_{(X,R)}$ is Borel. Indeed,

$\displaystyle B_{(X,R)}$
$\displaystyle=\bigcap_{i\in\omega}\\{(k,y)\in\operatorname{\omega^{\omega}}\times
X^{\omega}:k_{i}<k_{i+1}\land y(k_{i})Ry(k_{i+1})\\}$
$\displaystyle=\bigcap_{i\in\omega}\bigcup_{a\in\omega}\bigcup_{b>a}\big{(}\\{k\in\operatorname{\omega^{\omega}}:k_{i}=a,k_{i+1}=b\\}\times\\{y\in
X^{\omega}:y(k_{i})Ry(k_{i+1})\\}\big{)}$
$\displaystyle=\bigcap_{i\in\omega}\bigcup_{a\in\omega}\bigcup_{b>a}\left[\\{k\in\operatorname{\omega^{\omega}}:k_{i}=a,k_{i+1}=b\\}\times\left(\bigcup_{(y_{1},y_{2})\in
R}\\{y\in X^{\omega}:y(a)=y_{1},y(b)=y_{2}\\}\right)\right]$

and $R$ is countable. Clearly, $L_{(X,R)}=\pi_{X^{\omega}}[B_{(X,R)}]$ is a
projection of a Borel set. So $L_{(X,R)}$ is analytic. ∎

In case when $X$ is finite, every sequence of elements of $X$ contains a
constant subsequence. This observation gives us following:

######  Fact 2.2.

If $X$ is finite and $R$ is a reflexive relation on $X$, then
$L_{(X,R)}=X^{\omega}$.

######  Fact 2.3.

For a countable set $X$ define $\Delta_{X}=\\{(x,x):x\in X\\}$. Then
$L_{(X,\Delta_{X})}$ is Borel.

###### Proof.

$\displaystyle L_{(X,\Delta_{X})}$ $\displaystyle=\\{y\in X^{\omega}:(\exists
k_{0}<k_{1}<\ldots)(\forall i\in\omega)(y(k_{i})=y(k_{i+1}))\\}$
$\displaystyle=\\{y\in X^{\omega}:(\exists x\in X)(\exists
k_{0}<k_{1}<\ldots)(\forall i\in\omega)(y(k_{i})=x)\\}$ $\displaystyle=\\{y\in
X^{\omega}:(\exists x\in X)(\forall n\in\omega)(\exists k>n)(y(k)=x)\\},$

what clearly gives us that $L_{(X,\Delta_{X})}$ is $G_{\delta\sigma}$. ∎

######  Question 1.

What is the precise complexity of $L_{(X,\Delta_{X})}$? Is it not
$F_{\sigma\delta}$?

Notice that for any poset $(X,\leq_{X})$ above result shows that, in order to
identify projection class of $L_{(X,\leq_{X})}$, we can focus on analyzing
strictly increasing sequences.

$L_{(X,\leq_{X})}=L_{(X,\Delta_{X})}\cup\\{y\in X^{\omega}:(\exists
k_{0}<k_{1}<\ldots)(\forall i\in\omega)(y(k_{i})<_{X}y(k_{i+1}))\\}.$

Now we can move to classification of linear orders in this problem. Because in
well orderings there are no infinite decreasing subsequences, below fact
follows:

######  Fact 2.4.

Assume that $\leq_{X}$ is a well ordering on (countable) $X$. Then
$L_{(X,\leq_{X})}=X^{\omega}$.

Now let us consider the set of integers equipped with a standard order $\leq$.
It is probably one of the simplest linear orders which is not a well ordering.

######  Fact 2.5.

The set $L_{(\mathbb{Z},<)}$ is $G_{\delta}$ and not $F_{\sigma}$.

###### Proof.

Observe that every strictly increasing sequence of integers is unbounded. So
we can write

$\displaystyle L_{(\mathbb{Z},<)}=\\{y\in\mathbb{Z}^{\omega}:(\exists
k_{0}<k_{1}<\ldots)(\forall i\in\omega)(y(k_{i})<y(k_{i+1}))\\}$
$\displaystyle=\\{y\in\mathbb{Z}^{\omega}:(\forall n\in\mathbb{Z})(\exists
k\in\omega)(y(k)>n)\\}$
$\displaystyle=\bigcap_{n\in\mathbb{Z}}\bigcup_{k\in\omega}\\{y\in\mathbb{Z}^{\omega}:y(k)>n\\}$
$\displaystyle=\bigcap_{n\in\mathbb{Z}}\bigcup_{k\in\omega}\bigcup_{m>n}\\{y\in\mathbb{Z}^{\omega}:y(k)=m\\},$

which is clearly a $G_{\delta}$ set as $\\{y\in\mathbb{Z}^{\omega}:y(k)=m\\}$
is clopen.

Now note that both $L_{(\mathbb{Z},<)}$ and $L_{(\mathbb{Z},<)}^{c}$ have
empty interiors (since they cannot include any base open set). Therefore
$L_{(\mathbb{Z},<)}^{c}$ is meager (as an $F_{\sigma}$ set without interior).
If $L_{(\mathbb{Z},<)}$ is an $F_{\sigma}$ set, it is also meager
contradicting Baire category theorem. ∎

From the observation made after 2.3 and above fact we obtain following
corollary:

######  Corollary 2.6.

The set $L_{(\mathbb{Z},\leq)}$ is Borel.

##  3\. Main results

One of the tools in recognizing
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete sets among the sets of the
form $L_{(X,R)}$ is the following observation.

######  Theorem 3.1.

Suppose $(X,\leq_{X})$, $(Y,\leq_{Y})$ are posets and $\varphi:X\rightarrow Y$
satisfies the following condition for every $(x_{n})_{n\in\omega}\in
X^{\omega}$:

$(x_{n})_{n\in\omega}\text{ contains $\leq_{X}$-increasing
subsequence}\Leftrightarrow(\varphi(x_{n}))_{n\in\omega}\text{ contains
$\leq_{Y}$-increasing subsequence}.$

If $L_{(X,\leq_{X})}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete,
then $L_{(Y,\leq_{Y})}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete
too.

###### Proof.

Let $Z$ be a Polish space and $A\subseteq Z$ be an analytic set. There is a
Borel map $f:Z\rightarrow X^{\omega}$ such that $f^{-1}[L_{X}]=A$. We need a
Borel map $h:Z\rightarrow Y^{\omega}$ satisfying $h^{-1}[L_{Y}]=A$.

Define $g:X^{\omega}\rightarrow Y^{\omega}$ with formula

$g(x)(n)=\varphi(x_{n}).$

Clearly, $g$ is continuous, so $h=g\circ f$ is Borel. For the thesis it is
sufficient to show that $g^{-1}[L_{Y}]=L_{X}$.

$\displaystyle x\in L_{(X,\leq_{X})}$ $\displaystyle\Leftrightarrow x\text{
contains a $\leq_{X}$-increasing subsequence}$ $\displaystyle\Leftrightarrow
g(x)\text{ contains a $\leq_{Y}$-increasing subsequence}$
$\displaystyle\Leftrightarrow g(x)\in L_{(Y,\leq_{Y})}\Leftrightarrow x\in
g^{-1}[L_{(Y,\leq_{Y})}]$

∎

######  Corollary 3.2.

Assume that $X\subseteq Y$, $S\subseteq Y\times Y$, $R=S\cap(X\times X)$ and
$L_{(X,R)}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete. Then
$L_{(Y,S)}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete, too.

###### Proof.

It is enough to take $\varphi(x)=x$ in Theorem 3.1. ∎

######  Corollary 3.3.

Assume that $(X,\leq_{X})$ and $(Y,\leq_{Y})$ are isomorphic posets and
$L_{(X,\leq_{X})}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete. Then
$L_{(Y,\leq_{Y})}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete, too.

###### Proof.

To see this, put order isomorphism as $\varphi$ in Theorem 3.1. ∎

Let us now show an example of
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete set based on a space of
finite sequences of naturals.

######  Theorem 3.4.

The set $L_{(\operatorname{\omega^{<\omega}},\subseteq)}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

###### Proof.

To prove that $L_{(\operatorname{\omega^{<\omega}},\subseteq)}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete we will construct a
continuous function
$f:\operatorname{Tr_{\omega}}\rightarrow(\operatorname{\omega^{<\omega}})^{\omega}$
such that
$f^{-1}[L_{(\operatorname{\omega^{<\omega}},\subseteq)}]=\operatorname{IF_{\omega}}$
First, fix an enumeration $\\{\sigma_{n}:n\in\omega\\}$ of
$\operatorname{\omega^{<\omega}}$ satisfying the following condition

$\sigma_{n}\subseteq\sigma_{m}\Rightarrow n\leq m.$

Now we can define the function $f$:

$f(T)(n)=\left\\{\begin{array}[]{ll}\sigma_{n},&\sigma_{n}\in T\\\
1^{n}0,&\sigma_{n}\notin T\end{array}\right..$

Clearly, if $T\in\operatorname{IF_{\omega}}$, then $f(T)$ contains
$\subseteq$-increasing subsequence, hence $f(T)\in
L_{(\operatorname{\omega^{<\omega}},\subseteq)}$. To prove the opposite
implication, let $a\in L_{(\operatorname{\omega^{<\omega}},\subseteq)}$,
$a_{i_{0}}\subseteq a_{i_{1}}\subseteq a_{i_{2}}\subseteq\ldots$,
$i_{0}<i_{1}<i_{2}<\ldots$. Take any $T\in f^{-1}(a)$. Notice that at most one
of $a_{i_{0}},a_{i_{1}},\ldots$ can be of the form $1^{n}0$ for some
$n\in\omega$, so without loss of generality all of them are elements of $T$
and form a strictly increasing sequence. But such a sequence of elements of
$T$ builds a branch in $T$, so $T\in\operatorname{IF_{\omega}}$. ∎

######  Theorem 3.5.

The set $L_{(\operatorname{2^{<\omega}}2,\subseteq)}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

###### Proof.

We will use Theorems 3.4 and 3.1. First, define function
$f:\omega\rightarrow\operatorname{2^{<\omega}}2$ with formula

$f(n)=a_{0}a_{0}a_{1}a_{1}\ldots a_{m}a_{m},$

where $n=(a_{0}a_{1}\ldots a_{m})_{2}$, i.e. $a_{0}a_{1}\ldots a_{m}$ is a
binary reprezentation of $n$. Now consider a function
$\varphi:\operatorname{\omega^{<\omega}}\rightarrow\operatorname{2^{<\omega}}2$
defined as:

$\varphi(b_{0}b_{1}\ldots
b_{n})=f(b_{0})^01^f(b_{1})^01^\ldots^01^f(b_{n})^01.$

$\varphi$ and $\varphi^{-1}$ are both increasing (with respect to ordering
defined by $\subseteq$), so $\varphi$ fulfills requirements of Theorem 3.1.
Hence, the thesis holds. ∎

On $\operatorname{\omega^{<\omega}}$ let us define an ordering
$\operatorname{\leq_{RL}}$ with the formula

$x\operatorname{\leq_{RL}}y\iff(\exists n\in\omega)(x=y\upharpoonright
n\lor(x\upharpoonright n=y\upharpoonright n\land x(n)>y(n))).$

Relation $\operatorname{\leq_{RL}}$ can be seen as the lexicographical order
on $\operatorname{\omega^{<\omega}}$ with modification, that order on $\omega$
is reversed.

######  Theorem 3.6.

$L_{(\operatorname{\omega^{<\omega}},\operatorname{\leq_{RL}})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

###### Proof.

We will construct a continuous function
$f:\operatorname{Tr_{\omega}}\rightarrow(\operatorname{\omega^{<\omega}})^{\omega}$
such that $f^{-1}[L_{X}]=\operatorname{IF_{\omega}}$. First, fix an
enumeration $\\{\sigma_{n}:n\in\omega\\}$ of $\operatorname{\omega^{<\omega}}$
like in proof of Theorem 3.4. Now we can define function $f$:

$f(T)(n)=\left\\{\begin{array}[]{ll}\sigma_{n},&\sigma_{n}\in T\\\
1^{n}0,&\sigma_{n}\notin T\end{array}\right..$

Clearly, if $T\in\textrm{IF}_{\omega}$, then $f(T)$ contains
$\operatorname{\leq_{RL}}$-increasing subsequence, hence $f(T)\in L_{X}$. Let
$a\in L_{X}$,
$a_{i_{0}}\operatorname{<_{RL}}a_{i_{1}}\operatorname{<_{RL}}a_{i_{2}}\operatorname{<_{RL}}\ldots$,
$i_{0}<i_{1}<i_{2}<\ldots$. Take any $T\in f^{-1}(a)$. Notice that at most one
of $a_{i_{0}},a_{i_{1}},\ldots$ can be of the form $1^{n}0$ for some
$n\in\omega$ (as
$0\operatorname{>_{RL}}10\operatorname{>_{RL}}110\operatorname{>_{RL}}\ldots$),
so without loss of generality all of them are elements of $T$ and
$|a_{i_{0}}|>0$.

Since $a_{i_{0}}$ is $\operatorname{\leq_{RL}}$-smallest of
$a_{i_{0}},a_{i_{1}},\ldots$, it must be the case that $a_{i_{0}}(0)\geq
a_{i_{j}}(0)$ for all $j\in\omega$. Therefore there are only finitely many
possible values for $a_{i_{j}}(0)$, so infinitely many of them start with the
same number, say $\tau(0)$. Analogically, from all $a_{i_{j}}$ which start
with $\tau(0)$ infinitely many have the same number at position $1$, say
$\tau(1)$. Continuing this way we obtain
$\tau\in\operatorname{\omega^{\omega}}$ such that for every $n\in\omega$ there
is $j\in\omega$ satisfying

$\tau\upharpoonright n\preceq a_{i_{j}},$

so (because $T$ is a tree and $a_{i_{j}}\in T$) $\tau\upharpoonright n\in T$.
It follows that $\tau$ is an infinite branch of $T$. ∎

Now let us focus on rational numbers with standard ordering. Notice that this
poset can be seen as ”the most complicated” among countable linear orderings,
since it contains an isomorphic copy of any countable linear order. Firstly,
we shall see that $(\mathbb{Q},\leq)$ generates
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete set, opposed to linear
orderings investigated in Section 2.

######  Theorem 3.7.

The set $L_{(\mathbb{Q},\leq)}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

###### Proof.

Define a function
$\varphi:\operatorname{\omega^{<\omega}}\rightarrow\mathbb{Q}$ with formula
($\varphi(\varepsilon)=0$)

$\varphi(a_{0}a_{1}a_{2}\ldots a_{n})=(0.\underbrace{00\ldots
0}_{a_{0}}1\underbrace{00\ldots 0}_{a_{1}}1\underbrace{00\ldots
0}_{a_{2}}1\ldots\underbrace{00\ldots 0}_{a_{n}}1)_{2}.$

Considering $\operatorname{\leq_{RL}}$ on $\operatorname{\omega^{<\omega}}$,
$\varphi$ and $\varphi^{-1}$ are clearly increasing. Therefore $\varphi$ is an
order isomorphism between
$(\operatorname{\omega^{<\omega}},\operatorname{\leq_{RL}})$ and
$(\varphi(\operatorname{\omega^{<\omega}}),\leq)$. Thus, the thesis follows
from Corollaries 3.2 and 3.3. ∎

Next, we would like to characterize all linear ordering which yields an
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete set. The following theorem,
as explained later, will serve as a main tool in our task.

######  Theorem 3.8.

Suppose $X\subseteq\mathbb{Q}\cap[0,1]$, $\leq_{X}=\leq\cap(X\times X)$. Let
$\overline{X}$ be the closure of $X$ in the Euclidean topology. We have two
possible cases.

  1. (1)

If $|\overline{X}|=\omega$, then $L_{(X,\leq_{X})}$ is Borel.

  2. (2)

If $|\overline{X}|=\mathfrak{c}$, then $X$ contains $\leq$-dense subset.

###### Proof.

Firstly, consider the case $|\overline{X}|=\omega$. For $g\in[0,1]$ define

$L_{g}=\\{y\in X^{\omega}:(\forall a\in X)((a<g)\rightarrow(\forall
N\in\omega)(\exists n>N)(a<y_{n}\leq g))\\}.$

We want to show that

$L_{(X,\leq_{X})}=\bigcup\\{L_{g}:\,g\in\overline{X}\\}.$

Take any $g\in[0,1]$, for which $L_{g}\neq\emptyset$, and $y\in L_{g}$. Let
$N_{0}=\max\\{n:y_{n}=g\\}$ (if such $n$ does not exist, $y$ contains a
constant subsequence, hence $y\in L_{(X,\leq_{X})}$) and take $k_{0}=N_{0}+1$.
From the definition of $L_{g}$ there is $k_{1}>k_{0}$ such that
$y_{k_{0}}<y_{k_{1}}<g$ (because $y_{k_{0}}\in X$, $y_{k_{0}}<g$).
Analogically we can find $k_{2}>k_{1}$ satisfying $y_{k_{1}}<y_{k_{2}}<g$.
Continuing this way we obtain a sequence $k_{0}<k_{1}<k_{2},\ldots$ defining
an increasing subsequence $(y_{k_{i}})_{i\in\omega}$ of $y$.

On the other hand, when $y\in L_{(X,\leq_{X})}$, it contains a non-decreasing
subsequence. But this subsequence is bounded (like the whole
$X\subseteq[0,1]$), so it converges to some $g\in\overline{X}$. Thus, $y\in
L_{g}$.

Note that, since $X$ is countable, $L_{g}$ is a Borel set for every
$g\in[0,1]$. So $L_{(X,\leq_{X})}$, as a countable union of $L_{g}$’s, is also
Borel.

Now let us focus on the second case, i.e. $|\overline{X}|=\mathfrak{c}$.
First, observe that if $[a,b]\in\overline{X}$ for some $a,b\in[0,1]$, $a<b$,
then $X\cap[a,b]$ is $\leq$-dense. Thus, assume that $\overline{X}$ does not
contain an interval. There is a perfect nowhere dense set
$C\subseteq\overline{X}$. Without loss of generality we can presume that
$0,1\in C$ (otherwise we consider interval $[a,b]$, where $a=\min C$, $b=\max
C$). We will represent $C$ i more convenient way. To do this we will
inductively construct a family
$\\{C_{\sigma}:\,\sigma\in\operatorname{2^{<\omega}}2\\}$ of closed intervals
and a family $\\{U_{\sigma}:\,\sigma\in\operatorname{2^{<\omega}}2\\}$ of open
intervals (similarly to the classical construction of the Cantor set).

We start with $C_{\varepsilon}=[0,1]$. Since $C$ is nowhere dense, we can take
a maximal open interval $U_{\varepsilon}=(a_{\varepsilon},b_{\varepsilon})$,
$U_{\varepsilon}\subseteq[0,1]$, disjoint with $C$. Hence,
$C\subseteq[0,a_{\varepsilon}]\cup[b_{\varepsilon},1]$. Next we see that
$a_{\varepsilon}\neq 0$ (and $b_{\varepsilon}\neq 1$), because otherwise $0\in
C$ would be an isolated point of perfect set $C$. Moreover, from maximality of
$U_{\varepsilon}$, $a_{\varepsilon},b_{\varepsilon}\in C$. Let us denote
$[0,a_{\varepsilon}]=C_{(0)}$, $[b_{\varepsilon},1]=C_{(1)}$, $l_{(0)}=0$,
$p_{(0)}=a_{\varepsilon}$, $l_{(1)}=b_{\varepsilon}$, $p_{(1)}=1$.

Assume now that $C_{\sigma}=[l_{\sigma},p_{\sigma}]$ has been already
constructed for some $\sigma\in\operatorname{2^{<\omega}}2$. Analogically as
in the previous point we choose a maximal open interval
$U_{\sigma}=(a_{\sigma},b_{\sigma})\subseteq[l_{\sigma},p_{\sigma}]$ disjoint
with $C$. We denote $l_{\sigma^0}=l_{\sigma}$, $p_{\sigma^0}=a_{\sigma}$,
$l_{\sigma^1}=b_{\sigma}$, $p_{\sigma^1}=p_{\sigma}$.

Taking

$C_{n}=\bigcup\\{C_{\sigma}:\,\sigma\in 2^{<\omega}\\\ |\sigma|=n\\}$

it is clear that $C=\bigcap_{n\in\omega}C_{n}$.

Therefore, if we put $\mathcal{U}=\\{U_{\sigma}:\sigma\in 2^{<\omega}\\}$,

(1) $C=[0,1]\backslash\bigcup\mathcal{U}.$

Furthermore

(2)
$\\{l_{\sigma}:\sigma\in\operatorname{2^{<\omega}}2\\}\cup\\{p_{\sigma}:\sigma\in\operatorname{2^{<\omega}}2\\}\subseteq
C.$

We will now consider two possibilities. First, $X$ contains dense-in-itself
set and second, $X$ does not contain dense-in-itself set.

In the first situation, $X$ contains a dense-in-itself set. Without loss of
generality $X$ is dense-in-itself (otherwise we repeat above construction for
closure of this dense-in-itself subset of $X$). $\overline{X}$ is then a
perfect set and does not contain an interval, thus is nowhere dense. Hence, we
can put $C=\overline{X}$. Consider a set

$P=X\backslash\\{p_{\sigma}:l_{\sigma+1}\in X\\},$

where $\sigma+1$ is a successor of $\sigma\in 2^{n}$ in lexicographical order
on $2^{n}$ (in other words binary adding $1$ to $\sigma$ and $111\ldots 11+1$
does not exist). We claim that $P$ is $\leq$-dense. Take any $a,b\in P$,
$a<b$. From the above construction there is
$\sigma\in\operatorname{2^{<\omega}}2$ such that

$a\leq p_{\sigma}<l_{\sigma+1}\leq b.$

First, assume that $a<p_{\sigma}$ and $l_{\sigma+1}<b$. If $p_{\sigma}\in X$
or $l_{\sigma+1}\in X$, claim clearly holds. Otherwise
$p_{\sigma}\in\overline{X}$, so there is $x\in X$ close to $p_{\sigma}$.
Therefore

$a<x<b.$

Second, presume that $a=p_{\sigma}$. From definition of $P$, $l_{\sigma+1}<b$.
Since $X$ is dense-in-itself, there is $x\in X$ satisfying $l_{\sigma+1}<x<b$.
If $x\in P$, claim holds. If not, $x=p_{\tau}<l_{\tau+1}\leq b$ for some
$\tau\in\operatorname{2^{<\omega}}2$. Again, there is $y\in X$ such that
$a<y<x$. When $y\in P$, claim holds. Otherwise $y=p_{\psi}$ and $l_{\psi+1}\in
P$ for some $\psi\in\operatorname{2^{<\omega}}2$. But then

$a<p_{\psi}<\underbrace{l_{\psi+1}}_{\in P}<x<b.$

The case $a<p_{\sigma}$, $l_{\sigma+1}=b$ is analogous to previous one.

Finally, consider a situation when $X$ does not contain any dense-in-itself
set. We start by proving that

(3) $\overline{X\backslash C}\supseteq C.$

Suppose not, so there is $z\in C$ such that $z\notin\overline{X\backslash C}$.
There exists an open interval $U=(l,p)\ni z$ disjoint with $X\backslash C$. As
$z\in C\subseteq\overline{X}$, $X\cap U\neq\emptyset$ and $X\cap U\subseteq
C\cap U$. We claim that $X\cap U$ is dense-in-itself. Take any $x\in X\cap U$
and $\varepsilon>0$. We want to find $y\in(x-\varepsilon,x+\varepsilon)\cap
U\cap X$. Since $x\in C\cap U$, it exists
$c\in(x-\varepsilon,x+\varepsilon)\cap U\cap C$. Because $c\in C$, we can find
$y\in X$ close to $c$, especially $y\in(x-\varepsilon,x+\varepsilon)\cap U\cap
X$. Therefore $X\cap U$ is dense-in-itself, which contradicts assumption that
$X$ does not contain such a set.

From equation 1 we see that

$X\backslash C=X\cap\bigcup\mathcal{U}=\bigcup\\{X\cap
U_{\sigma}:U_{\sigma}\in\mathcal{U}\\}.$

Let $Y$ be a selector of family $\\{X\cap
U_{\sigma}:U_{\sigma}\in\mathcal{U}\\}\backslash\\{\emptyset\\}$. We claim
that $Y$ is $\leq$-dense. Take any $a,b\in Y$, $a<b$. Take
$\sigma,\psi\in\operatorname{2^{<\omega}}2$, $\sigma\neq\psi$, such that $a\in
U_{\sigma}$, $b\in U_{\psi}$. There is $\tau\in\operatorname{2^{<\omega}}2$
satisfying $C_{\tau}=[l_{\tau},p_{\tau}]\subseteq[l_{\sigma^1},p_{\psi^0}]$
and $C_{\tau}\neq[l_{\sigma^1},p_{\psi^0}]$. Suppose that $l_{\tau}\neq
l_{\sigma^1}$ (case when $p_{\tau}\neq p_{\psi^0}$ is analogous). From 2 it
follows that $l_{\tau}\in C$, so (from 3) $l_{\tau}\in\overline{X\backslash
C}$. Thus, there is a sequence from $X\cap\bigcup\mathcal{U}$ convergent to
$l_{\tau}$. Hence, there is $\phi\in\operatorname{2^{<\omega}}2$ satisfying

$U_{\phi}\subseteq[l_{\sigma^1},p_{\psi^0}],X\cap U_{\phi}\neq\emptyset.$

Therefore there exists $x\in Y\cap X\cap U_{\phi}$. Clearly, $a<x<b.$ ∎

######  Theorem 3.9.

Let $(X,\leq_{X})$ be a linear order. $L_{(X,\leq_{X})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete if and only if $X$ contains
$\leq_{X}$-dense subset.

###### Proof.

First, note that every linear order can be embedded into
$(\mathbb{Q}\cap[0,1],\leq)$. Therefore, we can assume without loss of
generality that $X\subseteq\mathbb{Q}\cap[0,1]$, $\leq_{X}=\leq$.

Suppose that $L_{(X,\leq_{X})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete. From Theorem 3.8, $X$
contains $\leq$-dense subset. On the other hand, if $X$ contains $\leq$-dense
subset $Y$, $Y$ is order-isomorphic to $\mathbb{Q}$ (since $\mathbb{Q}$ is the
only, up to isomorphism, countable dense linear order). From Corollaries 3.2
and 3.3, $L_{(X,\leq_{X})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete. ∎

######  Corollary 3.10.

Let $\operatorname{\leq_{lex}}$ be the lexicographical order on
$\operatorname{2^{<\omega}}2$. Then
$L_{(\operatorname{2^{<\omega}}2,\operatorname{\leq_{lex}})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete.

###### Proof.

Consider set $A=\\{x^1:x\in\operatorname{2^{<\omega}}2\\}$, i.e. the set of
all sequences ending with $1$. We claim that this set is
$\operatorname{\leq_{lex}}$-dense. Take any
$\sigma^1\operatorname{<_{lex}}\tau^1$,
$\sigma,\tau\in\operatorname{2^{<\omega}}2$.

If $\sigma^1\subseteq\tau^1$, then

$\sigma^1\operatorname{<_{lex}}\sigma^10^{|\tau|-|\sigma|}1\operatorname{<_{lex}}\tau^1.$

Otherwise

$\sigma^1\operatorname{<_{lex}}\sigma^11\operatorname{<_{lex}}\tau^1.$

Hence, by Theorem 3.9,
$L_{(\operatorname{2^{<\omega}}2,\operatorname{\leq_{lex}})}$ is
$\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete. ∎

######  Question 2.

What is the characterisation of countable posets $(X,\leq_{X})$ such that
$L_{(X,\leq_{X})}$ is $\operatorname{\mathbf{\Sigma}_{1}^{1}}$-complete?

## References

  * [1] T. Jech Set theory, The Third Millennium Edition, 2002, Springer Berlin, Heidelberg
  * [2] Alexander S. Kechris Classical Descriptive Set Theory 1995, Springer-Verlag New York, Inc.
  * [3] Srivastava A course on Borel sets 1998, Springer-Verlag New York
  * [4] A. Bernshteyn On Baire measurable colorings of group actions, Ergodic Theory and Dynamical Systems, 41 (2021), 818-845
  * [5] O. Kurka The isomorphism class of $c_{0}$ is not Borel, Israel Journal of Mathematics, 231 (2019), 243-268
  * [6] M. Bojanczyk, T. Idziaszek, M. Skrzypczak Regular Languages of Thin Trees, Theory of Computing Systems, 58 (2016), 614-663