Building on @JohnPick's answer and my comment, but being a little bit more formal. The difference can be explained by the difference between parallel versus sequential processing, and the difficulty of the predicate being evaluated. Your specific question is answered by Treisman (1985) (which I summarize in the second section) but I try to provide a more general explanation.
Basic idea
Whenever we say "does the element have property $X$", we usually pick a very simple property for $X$, which can be checked quickly. On the other hand a predicate like "does not have property $Y$" becomes something like "has propert $\neg Y$" and is usually a much more difficult property to evaluate. Thus, I expect the main problem is not in the negation, but the fact that $X$ is usually much faster to evaluate than $\neg Y$. In general, we would expect similar effects with other experiments that use a very easy property $X$ versus a very difficult but still positive property $Z$.
However, if this was the only factor, we would only see a constant-factor slow-down, which would we expect to be interpreted as quantitative but not qualitative slow down. This is where we throw in parallel processing. If we assume that the vision system is capable of highly parallel processing, but the difficulty of the property evaluation involved must be very low or we need to switch to sequential processing. In a computer, think GPU: the GPU can do many many simple calculations in parallel, but we have to use the slower CPU to do difficult computations one at a time.
Relevant literature support
Classic work like Treisman (1985) suggests that my assumption of very bounded computations being done in parallel, while more complicated properties require attention and sequential processing is a reasonable one. In particular, Treisman completely answers your question:
It suggests that search for the presence of a visual primitive is automatic and parallel, whereas search for the absence of the same feature is serial and requires focused attention.
Testing the theory with non-negative properties
To test my whole theory we can consider the following experiments. We present the participant with $N$ integers $r_1, ... r_N$ arranged randomly in the visual field, each integer is colored $c_1, ... , c_N$. We ask one of two possible questions:
- Property $X$: Name a green number, or
- Property $Z$: Name a number divisible by $3$.
As we increase $N$ from $1$ up to some reasonable limit, we get a function of reaction times $f_X(N)$ and $f_Z(N)$ for the two cases:
If both predicates ($X$ and $Z$) are processed in the same way (i.e. ever both parallel or both sequential), then we expect that
$\forall N \; \frac{f_X(N)}{f_Z(N)} \approx \frac{f_X(1)}{f_Z(1)}$. In other words, we expect just a constant slow-down from the fact that checking in a single number is green is easier than checking if it is divisible by $3$.
If $X$ is processed in parallel, while $Z$ is not, then we expect $\forall N \; \frac{f_X(N)}{f_Z(N)} > \frac{f_X(N + 1)}{f_Z(N + 1)}$. In other words, as we add one more item to the visual field, the parallel processing is slowed down significantly less than the sequential processing.
