Re: How to compute "A1 x. .. x An subset B" fast if B is fixed?

I see that your problem is not typical because you must test if an
n-dimensional cube is contained in B. We are testing specials sets for
inclusion in B. This can let us reduce complexity.
Maybe a good thing to do is to compute the "maximal cubes" of B. I mean
computing the greatests sets such that you can write them as B1x...xBn
where Bi is included in {1,...,d}. Then you only have to test inclusion
of Ai in Bi, for i in {1,...,n} and for all maximal cubes.

I hope this can help. I don't if it has the needed complexity in the
worst case. Note also that you can spend some time computing the
maximal cubes (you didn't asked for this complexity in your question).

Good luck, and please post if you have a solution or more ideas.

Anvera

sasha mal wrote:
Let B be any fixed subset of {1,...,d}^n.
On a RAM, is there a representation of B of size polynomial in d and at
most exponential in n so that the following query can be answered in
time polynomial in d and n:
Let A1, ..., An be any subsets of {1,...,d}. Is A1 x ... x An subset B?

Can anyone help? Ideas, references are welcome.
Sasha.

.