Finding small sets of integers in which every element is a sum of two others
I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)

Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.

We can do that easily if we construct the same for N-1, and then add N to the resulting set.

For the base case of 23, we can start with your example set.

To bring the size down, we should be able to use a similar approach: 

Construct sets which contain 1, N and N-1.

We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows: 


If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.
If N is odd construct a set for N-1 and N to resulting set.


For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 &lt; N &lt;= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.

In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.

It might be interesting to prove some lower bounds in the case N is prime.