## 3 Problem Definition and Formulation
### Objective Function  
To optimize task offloading and resource management, the following objective function is designed to balance system delay minimization and resource utilization maximization within the distributed optimization framework. The objective function can be decomposed into local objective functions for each node, which are ultimately summed up into a global objective function. To better distinguish these two functions, corresponding constraint conditions are matched to each of them. The local objective function for each node \(i\) is based on the delay and resource consumption of the task assignments at that node. It is defined as follows:  
\[f_{i}(\mathbf{X})=\sum_{j=1}^{M}\delta_{ik}^{j}X_{ij}+\sum_{j=1}^{M}X_{ij}(c_ {i}+s_{i}+b_{i}) \tag{11}\]  
The first term \(\sum_{j=1}^{M}\delta_{ik}^{j}X_{ij}\) represents the transmission delay for tasks from node \(i\) to user terminal \(k\), where \(\delta_{ik}^{j}\) represents the transmission delay for task \(j\) from node \(i\) to user terminal \(k\), and \(X_{ij}\) is a binary variable indicating whether task \(j\) is assigned to node \(i\). The second term \(\sum_{j=1}^{M}X_{ij}(c_{i}+s_{i}+b_{i})\) represents the total resources (computational, storage, and bandwidth) used during task offloading, aiming to maximize resource utilization. The local objective function is primarily influenced by these node-level constraints as constraints (6), (7), and (8). The global objective function is the sum of the local objective functions across all nodes, representing the total system delay and resource consumption. It is defined as follows:  
\[f_{\text{global}}(\mathbf{X})=\sum_{i=1}^{N}f_{i}(\mathbf{X}) \tag{12}\]  
The global objective function includes the delays and resource consumptions for each node, aiming to optimize the overall performance of the system, which is primarily influenced by these global constraints as constraints in Equations (9) and (10), which ensure that the task scheduling and resource allocation meet the overall performance requirements of the system. Theorem 1: _The Problem defined in Equations (11) and (12) in STIN is NP-hard._  
Proof: We reduce the 3-dimensional matching (3 DM) problem to the task scheduling and resource allocation problem. Given three sets \(X=\{x_{1},x_{2},\ldots,x_{n}\}\), \(Y=\{y_{1},y_{2},\ldots,y_{m}\}\), and \(Z=\{z_{1},z_{2},\ldots,z_{p}\}\), and a collection \(T\subseteq X\times Y\times Z\), the 3 DM problem asks to find a subset \(M\subseteq T\) such that each element in \(X\), \(Y\), and \(Z\) appears exactly once in \(M\). To reduce 3 DM to the task scheduling problem, for each triple \((x_{i},y_{j},z_{k})\in T\), we define a task \(t_{ijk}\) with resource demands \((c_{ijk},s_{ijk},b_{ijk})=(1,1,1)\). These tasks must be assigned to satellite nodes, where each node represents an element from \(X\), \(Y\), or \(Z\). The task assignment is represented by a binary matrix \(\mathbf{X}\), where \(X_{ijk}=1\) indicates that task \(t_{ijk}\) is assigned to satellite node \(i\), and \(X_{ijk}=0\) otherwise. The objective function in the task scheduling problem is  
\[f_{\text{global}}(\mathbf{X})=\sum_{i=1}^{N}\sum_{j=1}^{M}\frac{d_{ij}}{b_{i}}X _{ij}+\sum_{i=1}^{N}\sum_{j=1}^{M}X_{ij}(c_{i}+s_{i}+b_{i}).\]  
We also enforce resource constraints:\[\sum_{j=1}^{M}X_{ij}t_{ij}^{c}\leq c_{i},\quad\sum_{j=1}^{M}X_{ij}t_{ij}^{s}\leq s _{i},\quad\sum_{j=1}^{M}X_{ij}t_{ij}^{b}\leq b_{i}.\]  
The task assignment matrix \(\mathbf{X}\) must ensure that each task is assigned exactly once, implying a matching in \(T\) and that each element in \(X\), \(Y\), and \(Z\) is covered by exactly one triple. This task scheduling problem corresponds to solving the 3 DM problem, where the task assignment directly mirrors the matching required in 3 DM. As 3 DM is NP-hard, the task scheduling and resource allocation problem is also NP-hard. Note: The NP-hardness of the task scheduling problem is due to the combinatorial nature of the problem.