## 5 Some Theoretical Considerations
### Complexity  
One way to estimate the complexity of a problem is to measure the computational work required to solve it. We can also use complexity to compare the difficulty of two problems or the effectiveness of two algorithms. For the tiling problem, some factors that might form a complexity measure on theoretical grounds include the number of unknowns, the number of constraints, and the number of free variables of the associated ILP problem.  
Recall that the number of binary matrices for a tiling problem yields the number of unknowns in the resulting linear system. When we apply checkerboard colouring techniques, if we use every parionino \(P_{i}^{+}\) and \(P_{i}^{-}\), for \(i=1,2,\ldots,F\), the number of unknowns in the linear systems for the parionino and polyomino tiling problems are the same. However, for each polyomino \(P_{i}\) when the corresponding parionino used to tile \(R\) is \(P_{i}^{+}\) or \(P_{i}^{-}\) (but not both), then the number of binary matrices (and hence the number of unknowns) in the linear system for the parionino tiling problem is usually reduced, compared to the corresponding polyomino tiling problem. However, it is possible to construct some problems where this is not the case (see Section 6.2).  
It is also worth considering in the multihedral case the role played by the number of constraints on the problem complexity. Each polyomino or parionino contributes a constraint to the associated linear systems. Assuming the ILP problem is feasible, then it is reasonable to assume from a computational perspective that the more constraints we have the better. This is because the linear systems are usually underdetermined, and so it is helpful if the augmented matrix is as close to full rank as possible. As we often have \(\widetilde{F}\geq F\) we expect the rank of the augmented matrix for many parionino tiling problems to be closer to the full rank than the augmented matrix for the polyomino tiling problem (even when the number of unknowns in the two systems is the same).  
Thus to summarize, it is reasonable when we consider both the number of unknowns and the number of constraints in an ILP problem, that in general, we see an improvement in the solvability of a parionino tiling subproblem compared to the solvability of the full (uncoloured) tiling problem. However, because of the complexity of the general tiling situation, we cannot prove the superiority either algorithmically or theoretically.  
After many experiments, none of these measures seem to provide a reliable work estimate when judged by the time it takes an ILP solver to handle the problem. This may in part be because the ILP solver has a variety of techniques available and there are many features of a problem hidden from our analysis, which makes a simple complexity formula impossible. The possibly hidden structure in an ILP problem either hinders or helps the ILP solver to find solutions [63; 64]. Without a complexity formula based on theoretical grounds, we use the runtime of a fixed computer system. In our experience, this produces a reliable, repeatable, and practical substitute for a complexity formula. Although runtimes differ depending on the computer architecture and even the software version, it allows us to make practical comparisons between different tiling problems, or between subproblems of the same tiling problem.