Are the sum of two numbers desired?
I believe you could reduce it to \$O(n\log{n}+m\log{n}+n m)\$ if you want.  

Sort the inputs, then iterate over the tests and for each one, do a two variable iteration over the inputs, where you start as close to the test value/2, and move one index in the increasing direction and the other in the decreasing direction depending on whether the sum is less than or greater than the test value.  

This is somewhat confusing, so a partial implementation is:

def one_test(sorted_array, test_value):

    index1 = index_just_under(sorted_array, test_value/2)
    index2 = index1 + 1

    while (index1&gt;=0) and (index2 &lt; len(sorted_array)):
        sum = sorted_array[index1] + sorted_array[index2];
        if sum == test_value:
            return True
        if sum &gt; test_value:
            index1 = index1 - 1
        else:
            index2 = index2 + 1

    return False


Function index_just_under would be an \$O(\log{n})\$ method to find our initial cut point.  It returns the number of entries in the array below the second parameter, minus 1.  Given a sorted array, a binary search can be used.

The rest of this one_test function is \$O(n)\$.  This function is executed \$m\$ times, and the initial sort is \$O(n\log{n})\$.

While this might be a poor savings of the two input arrays are the same size, if tests array is much smaller, this could be a big saving.

If you start the indexes at the 0 and len(sorted array) - 1, you might be able to eliminate the index_just_under() call, reducing the time by \$O(m\log{n})\$.  On the other hand, it would eliminate any early-outs in the \$O(n m)\$ loops.  Effectiveness could depend on your expected number ranges.