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)$ .