试证明在 ICM / LTM 模型定义下，传播最大化问题是个 NP-hard 问题。

在ICM / LTM模型定义下，我们将社交网络建模为图$G=(V,E)$，其中$V$是节点集合，$E$是边集合。每个节点$i$都有一个观察到的状态$s_i\in S_i$，其中$S_i$是节点$i$可能的状态集合。假设我们要在这个网络中选择$k$个节点进行种子传播，以最大化影响力传播的范围。

为了证明传播最大化问题是NP-hard问题，我们可以采用归约的方法。具体来说，我们可以将一个已知的NP-hard问题（例如集合覆盖问题）归约为传播最大化问题。

假设我们有一个集合覆盖问题：我们有一个集合$U$，以及一个包含$U$中所有子集的集合族$\mathcal{S}$，并且我们要选择尽可能少的集合来覆盖$U$。我们可以将其转化为传播最大化问题，具体如下：

1. 我们将集合$U$中的每个元素$i$都看作一个节点，即$V=U$。

2. 我们将每个集合$S\in\mathcal{S}$都看作一个观察到的状态，即对于$S\in\mathcal{S}$，$s_i=S$对于$i\in S$成立。

3. 我们将两个节点$i,j\in V$之间连边当且仅当它们对应的元素在某个集合中同时出现，即$(i,j)\in E$当且仅当存在$S\in\mathcal{S}$满足$i,j\in S$。

4. 我们将$k$的值设置为集合覆盖问题需要的最小集合数。

这样，我们得到了一个传播最大化问题的实例，它的解决方案可以转化为一个集合覆盖问题的解决方案。由于集合覆盖问题是NP-hard问题，因此传播最大化问题也是NP-hard问题。

因此，我们可以得出结论，在ICM / LTM模型定义下，传播最大化问题是NP-hard问题。