# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 2 Preliminaries and Terminology
This model permits both the some-layers simple folds and its reverse operation, which is actually some-layers simple unfold (referred to as simple folds and simple unfolds in the following) [5]. As mentioned before, it was proven that in a \(1\times n\) map with fixed unit lengths, the valid folded states of the simple folding-unfolding model are exactly the same with the valid folded states of _general-folding model_, and there must exist at least one simple folding-unfolding sequence to reach an arbitrary valid folded state, which contains no more than \(2\times n\) (un)folds. According to the method in [5], it can be further clarified that not only the final flat-folded state but also every reachable partly flat-folded state by general folds can definitely be reached by the simple folding-unfolding model. To make it clear, both the simple folding-unfolding model and the simple folding model of an \(m\times n\) map satisfy Conditions (1) and (2): (1) Index the layers from top to bottom, then each operation is applied to some top or bottom layers with consecutive indexes and is along a single line; (2) The state before or after an operation is always flat and in the shape of a rectangle. The difference between them is that every crease in the simple folding model can be only folded once and then never unfolded, whereas creases can be either folded or unfolded multiple times in the simple folding-unfolding model. It is evident that a folding following the simple folding model also follows the simple folding-unfolding model, and a folding following the simple folding-unfolding model also follows the general folding model. Namely, the inclusion relation of reachable final flat-folded states in Table 1 is evident. What we aim to prove is the \"proper\" part in the proper subset relation. The above viewpoint is about the range of final flat-folded states a folding model can reach in different problem contexts. Oppositely, we can also discuss whether a given overlapping order represents a real or unreal folded state of a folding model in a certain problem. That is to say, such a problem concerns the _validity of given overlapping orders (VOP)_. In [15], VOP considering the total order of \(m\times n\) squares in an \(m\times n\) map with the general folding model is proven to be linear-time solvable. However, such a result does not give enough hint on the computational complexity of the map folding problem because a flat-foldable map may have exponential flat-folded states. In [16; 17], two linear-time algorithms are proposed to decide: (1) the validity of overlapping orders given on all the squares of an \(m\times n\) map (Total VOP) using the simple folding-unfolding model; (2) the validity of boundary overlapping orders of an \(m\times n\) map (_Boundary VOP_) using the simple folding model, respectively. In this paper, we will provide the solutions to all the combinations of problem settings and types of models that remained untouched or unsolved. In other words, this work can be seen as a perfection of the evaluation of all these three models in different variations of map folding. Moreover, we will discuss the reachable final flat-folded states sets (the configuration space) of different models in different problems. Despite the same performance of all the models in \(1\times n\) maps (1D VOP), the equality relation over their reachable flat-folded states sets turns into strict inclusion relation as the map becomes two dimensional (i.e., Total VOP). Besides, even if we restrict the overlapping orders to only the boundary squares, the strict inclusion relation still keeps (i.e., Boundary VOP).