How can I prove the following problem is NP complete? The problem:
I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\{s_{i} ,s_{j}\} \in \mathbb{N}$. Also the pairs are only for $\displaystyle i\neq j$.
I have two numbers: $ $$\displaystyle b\in \mathbb{N}$, $\displaystyle p\in \mathbb{N}$.
The problem is to check wether it exist a combination of pairs such that:
$\displaystyle c_{1} +c_{2} +\dotsc +c_{m} \leqslant b$ and $\displaystyle g_{1} +g_{2} +\dotsc +g_{m} \geqslant p$. Where of course $\displaystyle c_{i} ,g_{i}$ are cost and gain of a used pair $s_i$.
To show it is NP-complete I have to show a Karp reduction.

There are some problems we've studies and so that I can use:
Clique, Composite, SAT - Satisfiability problem, 3SAT, CSAT, IS - Independent Set, VC - Vertex, Cover, DHC - Directed Hamilton Cycle, HC - Hamilton Cycle, DS - Dominating Set, SSS - Subset, Set, 3COL, Partition, Bin-Packing.
Since it's talking about a sum I thought of using Subset-sum. If I set $\displaystyle p=b=k$, and I set $\displaystyle c_{i} =g_{i}$ for each $\displaystyle i$, then it really is just a sum question, to find a combination of elements of sum $\displaystyle k$.
But what it's complicating it for me is that if I have $\displaystyle n$ elements, I will have $\displaystyle \frac{n^{2} -n}{2}$ pairs, and so these many different costs. How can I rewrite the $\displaystyle n$ elements of partition, into some $\displaystyle k$ elements here such that there are $\displaystyle \frac{k^{2} -k}{2} =n$ pairs?
I've thought maybe I can only assign the cost to the first $\displaystyle n$ elements, and then all the rest to $\displaystyle 0$, but then cost and gain must be natural numbers.
Any advice?
I think there is an easy reduction from Knapsack.

Knapsack:

Input: a list of couples (value, weight) $\{(v_1, w_1), …, (v_n,w_n)\}$, a maximum weight $W$, a target value $V$
Question: is there a subset $S \subset [\![1, n]\!]$ such that $\sum\limits_{i\in S} v_i \geq V$ and $\sum\limits_{i\in S} w_i \leq W$


Now given an input of knapsack, let's construct an input of your problem: add a $n+1$-th element, and consider:

$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $c\{i, j\} = \infty$  and $c\{i, n+1\} = w_i$
$\forall (i, j) \in [\![1, n]\!]$ with $i\neq j$, we set $g\{i, j\} = 0$  and $g\{i, n+1\} = v_i$
set $b = W$ and $p = V$

Then this instance has a solution of your problem if and only if the input of knapsack has a solution. Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem.