# Global Resource Scheduling for Distributed Edge Computing
## 3 System Formulation
### Computational Complexity Analysis  
For given \(I\), \(J,C,P,L\), we use \(S(I,J,C,P,L)\) to represent the solution function of the global resource scheduling problem of distributed edge computing. We have the following theorem:  
**Theorem 1**.: _Problem \(S(I,J,C,P,L)\) is NP-Hard._  
Let us prove theorem 1. According to definition 1, we define subproblem \(S^{\prime}\) of problem \(S\):  
**Definition 2**.: _Let \(J=1\), and in Formula (1), let \(\alpha=0,\max_{L}\). Therefore, the price \(P\) has no meaning for the objective function \(Q\), so the subproblem \(S^{\prime}(I,1,C,P,L)\) of problem \(S\) can be described as:_  
\[\max\sum_{i=0}^{I-1}\sum_{t^{\prime}=0}^{I-1}Q_{i,t^{\prime}}(0)\]  
_s.t. \(\forall C_{i,0}\leq 0\)_  
\[\sum_{i^{\prime}=0}^{I-1}X_{i,t^{\prime}}(0)\geq-C_{i,0} \tag{4}\]  
\[P_{i,0}\geq\sum_{i^{\prime}=0}^{I-1}X_{i,t^{\prime}}(0)\times P_{i^{\prime},0} \tag{5}\]  
_where \(Q_{i,t^{\prime}}(j)=\left\{\begin{array}{ll}\frac{1}{L_{i,t^{\prime}}}&L_{i,t^{\prime}}\
eq 0\\ 0&L_{i,j}=0\end{array}\right.\)_  
We have the following theorem:  
**Theorem 2**.: _Problem \(S^{\prime}(I,1,C,P,L)\) is NP-Hard._  
Proof.: To prove theorem 2, we need to find a known NP-C problem and then prove that the problem can be reduced to problem \(S^{\prime}\). A 0-1 knapsack problem is proposed and proved to be an NP-C problem [35].  
**Definition 3**.: _There are \(N\) items and a backpack with a capacity of \(K\). The weight of the \(i\)-th item is \(w[i]\), and the value is \(v[i]\). The function \(x[i]=\{1,0\}\) represents whether the item is packed. Then, the 0-1 knapsack problem is expressed as:_  
\[\max\sum_{i=0}^{N-1}(v[i]\times x[i])\] \[\text{s.t. }\sum_{i=0}^{N-1}(w[i]\times x[i])\leq K \tag{6}\]  
For given \(N\) items and knapsack capacity \(X\), we use the function \(G(N,K,w,v)\) to represent the 0-1 knapsack problem. For problem \(G\), any input \(N,K,w,v\), we will convert it to the input of \(S^{\prime}\); the principle is as follows:  
\[\boxed{\begin{array}{l}\text{For problem $S^{\prime}$, let $I=N+1$, $C_{0,0}=0$, $P_{0,0}=K$. $\forall i\in\{1,2,\ldots,I-1\}$, let $C_{i,0}=1$,}\\ P_{i,0}=w_{i-1}\text{, $L_{0,i  
According to Formula (5) of Definition 2, we have \(P_{0,0}\geq\sum_{i^{\prime}=0}^{I-1}X_{0,i^{\prime}}(0)\times P_{i^{\prime},0}\). In the input conversion principle(\(\bigstar\)), we have \(K\geq\sum_{i^{\prime}=1}^{I-1}x[i^{\prime}-1]\times w[i^{\prime}-1]\). Since \(I=N+1\), we have \(K\geq\sum_{i^{\prime}=0}^{N-1}x[i^{\prime}]\times w[i^{\prime}]\), which satisfies the Formula (6) of Definition 3. Therefore, the output of question \(S^{\prime}\) can be transformed into the output of question \(G\). \((\blacksquare)\)
2 Suppose that the problem \(G\) obtains an output result \(x\), satisfying Definition 3. \(\forall i\in\{0,1,\ldots,N-1\}\), let \(X_{0,i+1}(0)=x[i]\). According to Formula (6), we have \(\sum_{i=0}^{N-1}x[i]\times w[i]\leq K\). In the input conversion principle (\(\bigstar\)), we have \(\sum_{i=0}^{N-1}X_{0,i+1}(0)\times P_{i+1,0}\leq P_{0,0}\). Due to \(I=N+1\), we have \(\sum_{i=1}^{I-1}X_{0,i}(0)\times P_{i,0}\leq P_{0,0}\). Because only \(C_{0,0}=0\), we have \(\sum_{i^{\prime}=0}^{I-1}X_{0,i^{\prime}}(0)\geq 0=-C_{0,0}\), satisfying Formula (4), Definition 2. Therefore, the output of question \(G\) can be transformed into the output of question \(S^{\prime}\). \((\blacksquare)\)  
In conclusion, \((\blacksquare)\) and \((\blacksquare\blacksquare)\) indicate that problem of \(G\) and \(S^{\prime}\) having the same output. Because the input conversion process of \((\bigstar)\) is completed in polynomial time, Theorem 2 holds!  
Since it has been proven that \(S^{\prime}\) is an NP-hard problem, the more complex problem \(S\) must be an NP-hard problem. Theorem 1 holds.