Timeline for Proving that an equal partition does not exist
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2018 at 14:28 | vote | accept | Erel Segal-Halevi | ||
| Jul 10, 2018 at 6:45 | history | tweeted | twitter.com/StackCompSci/status/1016574093829828609 | ||
| Jul 9, 2018 at 23:08 | comment | added | Yuval Filmus | The paper Semantic versus syntactic cutting planes gives an unsolvable instance of subset sum which is provably hard to disprove in a particular proof system, cutting planes. | |
| Jul 9, 2018 at 21:57 | answer | added | D.W.♦ | timeline score: 7 | |
| Jul 9, 2018 at 20:10 | comment | added | mhum | If a universally applicable, polynomially verifiable certificate were available to certify negative instances of PARTITION (or, any other NP-complete problem), then we would have NP=co-NP which would be a massive breakthrough. Given that, it may be worth exploring methods that are either 1) super-polynomial in time complexity, or 2) not universally applicable (i.e.: only useful in some subset of cases). | |
| Jul 9, 2018 at 19:19 | history | asked | Erel Segal-Halevi | CC BY-SA 4.0 |