<p>Depends which NP hard problem. A famous one (e.g., 3SAT) would be a nice contribution. A random one of the 15k NP-hard problems would be less so.</p>

CC BY-SA 3.0
2018-02-14T21:42:51.600Z
2018-02-14T21:42:51.600Z
user48607
<p>There are venues that are interested by elegant proofs of existing results, see for instance the <a href="https://simplicityalgorithms.wixsite.com/sosa/cfp" rel="noreferrer">Symposium on Simplicity in Algorithms</a>.</p>

<p>So yes, in some cases an elegant proof can be considered as a contribution, especially if it offers new insights.</p>

CC BY-SA 3.0
2018-02-14T06:55:19.383Z
2018-02-14T06:55:19.383Z
Gopi
<p>I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the NP-hardness. I am wondering if this is considered as a contribution or not? I am trying to motivate my work but I didn't find a similar path.</p>

<p>I don't know if this is the right place to ask or should I go to academia? </p>

CC BY-SA 3.0
2018-02-10T23:05:38.423Z
Simplifying proofs is a standard (and sometimes useful) kind of contribution. See if your simple proof generalizes to prove something else NP hard (that perhaps wasn't already known)
Ryan Williams
CC BY-SA 3.0
2018-02-11T04:58:51.397Z
If you care enough about the simplification, you can always just write it down, and post it to the arxiv. If other people care, sooner or later it would get cited. Generally speaking getting such simplified proofs papers accepted to conferences/journals can be challanging.
Sariel Har-Peled
CC BY-SA 3.0
2018-02-13T19:11:58.830Z
Simplified proofs often involve/exploit a certain structure in the problem, so sometimes you get a stronger result in the form of "this problem is NP-hard even in the restricted case of ____".  If you are reducing from a different problem, it might be that you have further properties transferring over, such as hardness in approximability or parameterized complexity, so look for these sort of stronger observations. Even without any strengthening, I would say that an alternative proof is still a contribution, esp if it is simplified, but I do agree that it is a hard sell for some.
JimN
CC BY-SA 3.0
2018-02-16T11:21:45.103Z
Simpler proofs are always preferable in introductory or pedagocial texts. So you might want to write a review article or review chapter for an upcoming book on your area (if you're a student, supervisors usually know about or are involved in such activities) and say "Problem X was first shown to be NP-hard by Z, we give a simplified proof here:" Even if your proof is technically not the strongest one in some parameter, but *much* simpler than the formally best proof, your exposition might still be highly relevant for an introductory text.
Martin Schwarz
<research-practice><writing>
Is an NP-hardness proof of an NP-hard problem considered a contribution?
zdm
# Is an NP-hardness proof of an NP-hard problem considered a contribution?

(Asked by: username_0 on 2018-02-10)

I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the NP-hardness. I am wondering if this is considered as a contribution or not? I am trying to motivate my work but I didn't find a similar path.

I don't know if this is the right place to ask or should I go to academia?

**Tags:** research-practice, writing

> **Comments:**
> **username_1**: Simplifying proofs is a standard (and sometimes useful) kind of contribution. See if your simple proof generalizes to prove something else NP hard (that perhaps wasn't already known)  
> **username_2**: If you care enough about the simplification, you can always just write it down, and post it to the arxiv. If other people care, sooner or later it would get cited. Generally speaking getting such simplified proofs papers accepted to conferences/journals can be challanging.  
> **username_3**: Simplified proofs often involve/exploit a certain structure in the problem, so sometimes you get a stronger result in the form of "this problem is NP-hard even in the restricted case of ____".  If you are reducing from a different problem, it might be that you have further properties transferring over, such as hardness in approximability or parameterized complexity, so look for these sort of stronger observations. Even without any strengthening, I would say that an alternative proof is still a contribution, esp if it is simplified, but I do agree that it is a hard sell for some.  
> **username_4**: Simpler proofs are always preferable in introductory or pedagocial texts. So you might want to write a review article or review chapter for an upcoming book on your area (if you're a student, supervisors usually know about or are involved in such activities) and say "Problem X was first shown to be NP-hard by Z, we give a simplified proof here:" Even if your proof is technically not the strongest one in some parameter, but *much* simpler than the formally best proof, your exposition might still be highly relevant for an introductory text.  

---

## 2 answers

### Answer by username_6 on 2018-02-14. Score: 14 | Accepted answer

There are venues that are interested by elegant proofs of existing results, see for instance the [Symposium on Simplicity in Algorithms](https://simplicityalgorithms.wixsite.com/sosa/cfp).

So yes, in some cases an elegant proof can be considered as a contribution, especially if it offers new insights.


---

### Answer by username_5 on 2018-02-14. Score: -2

Depends which NP hard problem. A famous one (e.g., 3SAT) would be a nice contribution. A random one of the 15k NP-hard problems would be less so.


---

