## 2 Overview of the Basic Concepts of Wind Farm Design and Optimization
### The Computational Complexity of the WFDO Problem
A common characteristic of such problems is that they do not have a known efficient solution procedure. Although some authors, based on the terminology proposed by the computational complexity theory, have claimed that the WFDO problem falls into the NP-hard (see Section 4.5 for misconceptions) class problems (problems that are at least as hard as any NP problem) [152, 153, 154] no formal proof has been given. Therefore, this section provides a formal derivation of the NPO-completeness [146, 147, 155] of the WFDO problem. Independently of the considered instance, the WFDO problem design variables, although bounded, describe an infinite search space. However, depending on the assumptions made (e.g., discretization of the available WT positions within the wind farm site as a function of a predefined minimum allowed distance between WTs), the WFDO problem may fall into the class of problems known as combinatorial optimization problems. Let us suppose the simplest version of the WFDO problem (the Linear Wind Farm Design and Optimization (LWFDO) problem [27, 156, 157]) where WTs are located in a flat discretized straight line, having \(n\) discretized segments, which is parallel to unidirectional wind speed. Note that the domain discretization can be uniform or non-uniform as long as the minimum safety distances between WTs are respected. WTs are considered to be of the same height, size, type, and operate in steady state conditions with constant thrust and power coefficients without regard to the inflow condition, but respecting the Betz-Lanchester theoretical limit [158]. No auxiliary infrastructure (e.g., roads or power lines) is to be built, and no other economic or environmental aspects are taken into account. Constant, isotropic free-stream air properties (e.g., density) and wind speed in a neutral atmosphere are assumed. Uniform surface roughness is also assumed. The mono-objective function to be maximized is the total instantaneous mechanical power conversion (see Sections 3.1.1 and 3.1.2 for details) of the wind farm (defined as the sum of the power conversion of all the WTs, which can be determined using Equation (2)), while considering wake effects (e.g., the Jensen-Katic wake model, Equations (15) and (39), and the wake superposition by sum of squares of velocity deficits method, Equation (41), are assumed). The design variables (\(x_{i}\in\{0,1\},\forall i\in\{1,2,...,n\}\)) represent if a WT is located or not on each discretized space. By summing up all the elementary operations needed to quantify the instantaneous power conversion of a linear wind farm, consisting of \(2\leq m\leq n\) WTs, (_i.e._, employing Equations (2), (15), (39), and (41)), an expression that quantifies the total computational time required to evaluate the performance of the linear wind farm was derived, as shown in Equation (1):  
\[T_{\text{LWFDO}}(m)=(5.5m^{2}+3.5m-5)\gamma \tag{1}\]  
where \(\gamma\) is a factor representing the time required to perform an elementary operation. The LWFDO problem lies within the NPO class, since for a given configuration of \(m\) WTs, the mono-objective function can efficiently (in polynomial time) quantify the total instantaneous mechanical power conversion of the wind farm (considering the simplicity of the physical models and their limitations). Considering other currently available engineering wake models and/or wake superposition methods will modify the resultant coefficient values of Equation (1) but will not affect the maximum order of the polynomial. The LWFDO problem can be easily transformed into a _decision problem_ (LWFD) by translating the main objective (_i.e._, obtaining the maximum power conversion) into the objective of determining if concrete questions are _true_ or _false_ (e.g., given a specific instance, is there a linear array of WTs that can convert \"at least/at most/more than/less than\" \(k\) amount of mechanical power from wind?). The LWFD _decision problem_ lies within the NP class, as it has the same elementary operation requirements as the LWFDO problem.