Timeline for poly-time algorithm to choose elements of sets
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2010 at 13:08 | vote | accept | simone | ||
| Jun 11, 2010 at 10:51 | comment | added | simone | Thanks to everybod and particularly to Darij for the reduction from SAT. Not quite what I had hoped for, but at least I now know that there "no" hope for a polynomial-time algorithm. | |
| Jun 10, 2010 at 20:13 | comment | added | Joel David Hamkins | Yes, I think this is required, since otherwise you won't have a polynomial reduction. | |
| Jun 10, 2010 at 18:38 | comment | added | darij grinberg | Thanks. In fact I intuitively perceived the size of the clauses to be "really small" compared to their number ;) | |
| Jun 10, 2010 at 18:38 | history | edited | darij grinberg | CC BY-SA 2.5 |
added 4 characters in body; added 3 characters in body
|
| Jun 10, 2010 at 18:29 | comment | added | Joel David Hamkins | But perhaps you should use 3-SAT or other bounded size disjunctions, to avoid the blow-up in size that comes from taking all nonempty subsets for $B_i$? | |
| Jun 10, 2010 at 18:22 | history | answered | darij grinberg | CC BY-SA 2.5 |