Minimal union of cartesian products
- From: sashaDOTmal <sashaPUNKTmal@xxxxxxxxxx>
- Date: Wed, 01 Mar 2006 15:28:11 +0100
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
2. We generalize the problem to more dimensions.
Let X1,..., Xn be finite sets. The algorithm for the following problem
is needed.
Given a subset Q of the cross product X1 x ... x Xn, find the smallest
natural number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
Could anyone help?
Regards,
sasha
.
- Follow-Ups:
- Re: Minimal union of cartesian products
- From: Ken Pledger
- Re: Minimal union of cartesian products
- Prev by Date: Re: "Deal or No Deal" arithmetic
- Next by Date: Re: "Deal or No Deal" arithmetic
- Previous by thread: Somme irrationnelle
- Next by thread: Re: Minimal union of cartesian products
- Index(es):
Relevant Pages
|
