Timeline for Original proofs generated on the parent site
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Dec 10, 2010 at 3:46 | comment | added | Tsuyoshi Ito | Thanks for rolling it back. I see your point, but if I am not mistaken, the phrase “original proofs” usually refers to something that can be considered as a result by itself, and it has to be more than a mere observation. The distinction between a result and an observation is not always black-and-white: there are cases where it is difficult to tell which. But in my opinion, the relation between the problem commented by Jukka and the Cluster Editing problem studied in the paper is undoubtedly an observation. Maybe my answer confused you because the observation was too verbose. | |
| Dec 10, 2010 at 3:27 | history | rollback | Hsien-Chih Chang 張顯之 |
Rollback to Revision 1
|
|
| Dec 10, 2010 at 3:26 | comment | added | Hsien-Chih Chang 張顯之 | @Tsuyoshi: Ok, I'll rollback the answer. That comes up another question - what kind of proofs that count as an original one? I've never seem the relation you mentioned before, and to me that counts as original. Maybe we need a more precise definition as a standard to put some proofs into this post. | |
| Dec 10, 2010 at 3:25 | comment | added | Aaron Sterling | I'm glad we're having this discussion. I was on the fence about including the various reductions that have appeared. I've been busy, so I haven't gone back through the site at all, but I guess @Tsuyoshi's is saying that something more than a straightforward reduction is required to be listed here. I'm ok with that, but listing reductions seems ok too, because it might be useful for future articles, publicity at conferences etc. | |
| Dec 10, 2010 at 3:16 | comment | added | Tsuyoshi Ito | The current question asks original proofs, and as I said, I do not think that my answer counts as an original proof. Therefore, despite that it is nice of you to have mentioned my answer, I do not think that my answer belongs here. | |
| Dec 10, 2010 at 3:11 | comment | added | Hsien-Chih Chang 張顯之 | @Tsuyoshi: Then how if I change the phrase to "provide a connection between a special case of the problem and a known NP-complete result proved by Shamir et al.?" | |
| Dec 10, 2010 at 3:03 | comment | added | Tsuyoshi Ito | Thanks for mentioning my answer, but my answer is not an original proof. It is a reference to a known NP-completeness result. The equivalence of the special case of the asked problem to the problem studied in the paper is just an observation. Therefore I do not think that it would be fair to the authors of the paper for me to claim that I showed that the special case is NP-complete. | |
| Dec 10, 2010 at 2:53 | history | edited | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |
special case added
|
| Dec 10, 2010 at 1:08 | history | answered | Hsien-Chih Chang 張顯之 | CC BY-SA 2.5 |