18
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 15
    $\begingroup$ 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) $\endgroup$ – Ryan Williams Feb 10 '18 at 23:05
  • 8
    $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Feb 11 '18 at 4:58
  • 8
    $\begingroup$ 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. $\endgroup$ – JimN Feb 13 '18 at 19:11
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Schwarz Feb 16 '18 at 11:21
14
$\begingroup$

There are venues that are interested by elegant proofs of existing results, see for instance the Symposium on Simplicity in Algorithms.

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

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.