[Computational Complexity] NP-Completeness Papers
A colleague is refereeing a paper in a non-computer science area that shows a certain computational problem is NP-complete. The proof uses a simple reduction from a standard NP-complete problem. Should such a result be published? As long as people really care about the computational problem, then yes, such results should be published.
The greatest gift of computational complexity to society is the ability to use NP-completeness to show that a large variety of problems are likely hard. The field has also developed many tools to help easily show such problems are NP-complete. We shouldn't penalize people for using these tools.
This is one of those cases where having a "simple proof" hurts the paper. If the paper used PCP technology in the proof it would without question be published. And if the paper relied on the unique games conjecture (and thus a weaker result) the paper would likely get accepted into STOC.
Posted by Lance to Computational Complexity at 10/08/2005 11:38:00 AM