# Most efficient method for set intersection

Suppose I have two finite sets, $$A$$ and $$B$$, with arbitrarily large cardinalities, the ordered integral elements of which are determined by unique (and well defined) polynomial generating functions $$f:\mathbb{N}\rightarrow\mathbb{Z}$$ given by, say, $$f_1(x_i)$$ and $$f_2(x_j)$$, respectively. Assume, also, that $$A\cap B$$ is always a singleton set $$\{a\}$$ such that $$a=f_1(x_i)=f_2(x_j)$$ where I’ve proven that $$i\neq j$$.

Assuming you can even avoid the memory-dump problem, it seems the worst way to find $$\{a\}$$ is to generate both sets and then check for the intersection. I wrote a simple code in Sagemath that does this, and, as I suspected, it doesn’t work well for sets with even moderately large cardinalities.

Is there a better way to (program a computer to) find the intersection of two sets, or is it just as hopeless (from a time-complexity perspective) as trying to solve $$f_1(x_i)=f_2(x_j)$$ directly when the cardinalities are prohibitively large? Is there a parallel-computing possibility? If not, perhaps there’s a way to limit the atomistic search based on a range of values—i.e., each loop terminates the search after it finds the first $$i$$ value such that $$f_1(x_i)>f_2(x_j)$$, knowing that $$f_1(x_{i+1}), f_1(x_{i+2}), f_1(x_{i+3}), \cdots, f_1(x_{i+n})>f_1(x_i)>f_2(x_j)$$.

Posted on Categories proxies