Timeline for Cartesian factorization of a finite set of n-tuples
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 30, 2011 at 0:30 | answer | added | kjo | timeline score: 1 | |
| Jan 29, 2011 at 11:41 | history | edited | kjo | CC BY-SA 2.5 |
simplified problem statement; clarified some definitions
|
| Jan 29, 2011 at 3:07 | comment | added | Gerhard Paseman | I suspect that this is related to NP hard problems such as exact cover or 3 dimensional matching. What I find interesting is that you need few witnesses to "block" such factorizations. For example, if for all appropriate partial tuples y the tuple corresponding to a_1,a_2,y is not in X, then X will not be factorizable as A1x A2 x whatever. It reminds me of logic minimization of an almost boolean function (some inputs may receive a don't care value as output) and its (almost) complement. Gerhard "Anyone Remember Programmable Logic Devices?" Paseman, 2011.01.28 | |
| Jan 29, 2011 at 2:33 | history | asked | kjo | CC BY-SA 2.5 |