Re: Minimal union of cartesian products


Do the following two copies of the same question come from a
mathematics olympiad or some such contest? If so, we'd better not
answer them in the meantime.

Ken Pledger.



In article <du4b1r$3buf2$1@xxxxxxxxxxxxxxxxxxxxxxxx>,
sashaDOTmal <sashaPUNKTmal@xxxxxxxxxx> wrote:

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



In article <du44bh$35s1s$1@xxxxxxxxxxxxxxxxxxxxxxxx>,
Alexander Malkis <malkis@xxxxxxxxxxxxx> wrote:

Hello 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}.
.

Relevant Pages

  • Re: Representation as union of cartesian products
    ... number k so that Q is equal to the union of k cartesian products. ... What is the time complexity of the corresponding problem, ... Given a subset Q of the cross product X1 x ... ... natural number k so that Q is equal to the union of k cartesian products. ...
    (sci.math)
  • Minimal union of cartesian products
    ... The algorithm for the following problem is ... number k so that Q is equal to the union of k cartesian products. ... Given a subset Q of the cross product X1 x ... ... natural number k so that Q is equal to the union of k cartesian products. ...
    (sci.math)
  • Representation as union of cartesian products
    ... The algorithm for the following problem is ... number k so that Q is equal to the union of k cartesian products. ... Given a subset Q of the cross product X1 x ... ... natural number k so that Q is equal to the union of k cartesian products. ...
    (sci.math)
  • Re: Question about Date & Darwen operator
    ... When the operands have the same heading, then this is the same as a traditional SQL UNION, except that all duplicates are always removed. ... in A cross product Tb) ... D & D call it a formal definition. ... personally, i like the connection with ordinary English, even if i'm often getting the result of wrong! ...
    (comp.databases.theory)