I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. Nevertheless I don't understand why it is NP-complete, it seems to me that I can solve it in polynomial time.
Let's consider specific example:
We have two tables, $T_1$ and $T_2$, where $|T_1|=m$ and $|T_2|=n$.
Now, let $t$ will be a tuple $t=(a,b,c)$. Then I can easily give polynomial algorithm for checking if join of $T_1$ and $T_2$ containg tuple $t$.
Is is sufficient to get $T_1\times T_2$ and in linear time check if this tuple is contained in result. Please note that size of $|T_1\times T_2|=n\times m$ is polynomial.
Where am I wrong?