## 4 Problem Formulation and Algorithm Proposed
### Problem of Minimum Network Cost Transducer Orientation
#### 4.1.2 NP-Complete of MNCTO Problem  
In underwater environment, the path loss that occurs over a distance \(l\) for a signal of frequency \(f\) is given by the following [30]:  
\[A(l,f)=A_{0}l^{k}a(f)^{l} \tag{18}\]  
where \(A_{0}\) is a unit-normalized attenuation constant, \(k\) is the spreading factor ranging from \(1\) to \(2\), and \(a(f)\) is the absorption coefficient. Thus, the acoustic path loss expressed in \(dB\) is given by the following:  
\[10\log\frac{A(l,f)}{A_{0}}=k\log l+l\log a(f) \tag{19}\]  
Fixing the signal frequency, we can treat the absorption coefficient \(a(f)\) as a constant, and the energy cost that a signal travels for a distance of \(l\) can be denoted in unit \(dB\) as the following:  
\[cost(l)=K\log l+Al \tag{20}\]  
where the capitalized letters represent constant coefficients. Then, the problem of MNCTO is formulated as follows:  
**Problem 2**.: _Given a set of nodes \(V\) with a \(\pi/3\) beamwidth transducer and a total energy consumption \(\mathcal{E}\), can a network be symmetrically connected by assigning to each node a suitable orientation and transmission range \(R\)?_  
**Theorem 2**.: _The MNCTO problem is also NP-complete._  
Proof.: In order to prove that MNCTO is NP-complete, we firstly prove \(MNCTO\in NP\), and then prove that MNCTO is NP-hard by reducing the former proven \(TOP\leq_{P}MNCTO\).  
For proof of \(MNCTO\in NP\), it can be easily determined whether the network is symmetrically connected under constraint of total cost \(\mathcal{E}\) in polynomial time. Given a certification of \(\mathcal{C}=[C_{1},C_{2},...,C_{n}]\), \(n=\|V\|\), where \(C_{i}=[o_{i},cost_{i\to j}]\) is a tuple, denotes the cost of node \(i\) communicating to its adjacent node \(j\) with orientation \(o_{i}\).  
In order to reduce \(TOP\leq_{P}MNCTO\), we recall the previous structure of HPHGG, whose vertexes are replaced by equilateral triangular widgets in Figure 7 and make a further analysis. Assuming that the side lengths of the triangular and the regular hexagon are identical, \(r\), the inner edges of the widgets are of length \(r/2\) and the edges connecting the two widgets are of length \(r\), so the according costs are as follows:  
\[cost(r) =K\log r+Ar\] \[cost(\frac{r}{2}) =K\log\frac{r}{2}+A\frac{r}{2} \tag{21}\] \[=K\log r+\frac{Ar-K\log 2}{2}\]  
From Lemma A1, we know a widget can only connect to its adjacent peers; in fact, only in this way does it cost the minimum energy. According to the concept of the Hamiltonian path, we obtain the number of edges outside the widgets as \(n-1\), while in order to connect them, the links inside have to be added.  
The relationship between number of nodes \(n\) and the cost of the inner widget is investigated in the following, which is shown in Lemma A2. Thus, the minimum total cost of the whole HPHGG for TOP can be obtained as follows:  
\[\mathcal{COST} =C_{t}+(n-1)cost(r)\] \[=\frac{(6n-7)(5K\log r+3 Ar-2K)+K\log 2}{5} \tag{22}\]Hence, the reduction is conducted.  
Recalling Problem 2, if a TOP has a Hamilton Path, the minimum cost \(\mathcal{COST}\) is obtained, and if \(\mathcal{COST}\leq\mathcal{E}\), the network can be symmetrically connected by assigning to each node a suitable orientation and transmission range \(r\), but not the opposite.