<p>I'm reading this paper, <a href="http://portal.acm.org/citation.cfm?id=1556167" rel="nofollow">A simple NP-hard problem by Demontis</a>, where he defines an interesting $NP$-hard set and finally he conclude with this theorem:</p>

<blockquote>
  <p>Theorem: $P=NP$  if and only if it is possible to calculate in polynomial time all the
  fundamental elements of any formula.</p>
</blockquote>

<p>The paper does not have an abstract and I'm kind of lost because of the new terminology used in the paper.</p>

<blockquote>
  <p>Could you explain the significance of this paper? Do the fundamental elements of a formula represent the variables that have true value in every satisfying assignment? Does this theorem represent a new result? What are the insights into the $P$ vs $NP$ problem presented in the paper? </p>
</blockquote>

<p>ACM SIGACT News, Volume 40 Issue 2, June 2009</p>

CC BY-SA 2.5
2010-11-18T23:19:55.307Z
Are questions of the form "Could you explain the significance of paper X" on-topic here? In particular, if X isn't a peer-reviewed scientific article? People could generate thousands of such questions, and each of them would be of very little interest to the users of this site.
Jukka Suomela
CC BY-SA 2.5
2010-11-18T23:30:10.087Z
@Jukka, As far as I know, ACM SIGACT News is peer-reviewed. Correct me if I'm wrong.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-18T23:52:59.337Z
@Jukka, Are you suggesting that questions regarding ACM SIGACT News articles are off-topic?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-18T23:59:46.397Z
SIGACT News may not be peer-reviewed to the same extent that J.ACM is, but articles in it are certainly supposed to be screened adequately enough that they are not complete nonsense. So I think this question is on-topic. I have to admit I can't follow that paper either, although I haven't tried that hard.
Peter Shor 
CC BY-SA 2.5
2010-11-19T00:05:05.707Z
@Turkistany, as for your last question, if this article presented any real new insight into the P vs NP question, it would almost certainly have appeared in a more prestigious publication than SIGACT News.
Peter Shor 
CC BY-SA 2.5
2010-11-19T00:18:05.007Z
Thanks Peter for clarifying it. My gut feeling tells me there is something original in this paper. I could be wrong.
Mohammad Al-Turkistany
<cc.complexity-theory>
A simple NP-hard problem
Mohammad Al-Turkistany
# A simple NP-hard problem

(Asked by: username_0 on 2010-11-18)

I'm reading this paper, [A simple NP-hard problem by Demontis](http://portal.acm.org/citation.cfm?id=1556167), where he defines an interesting $NP$-hard set and finally he conclude with this theorem:

> Theorem: $P=NP$ if and only if it is possible to calculate in polynomial time all the
> fundamental elements of any formula.

The paper does not have an abstract and I'm kind of lost because of the new terminology used in the paper.

> Could you explain the significance of this paper? Do the fundamental elements of a formula represent the variables that have true value in every satisfying assignment? Does this theorem represent a new result? What are the insights into the $P$ vs $NP$ problem presented in the paper?

ACM SIGACT News, Volume 40 Issue 2, June 2009

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: Are questions of the form "Could you explain the significance of paper X" on-topic here? In particular, if X isn't a peer-reviewed scientific article? People could generate thousands of such questions, and each of them would be of very little interest to the users of this site.  
> **username_0**: @Jukka, As far as I know, ACM SIGACT News is peer-reviewed. Correct me if I'm wrong.  
> **username_0**: @Jukka, Are you suggesting that questions regarding ACM SIGACT News articles are off-topic?  
> **username_2**: SIGACT News may not be peer-reviewed to the same extent that J.ACM is, but articles in it are certainly supposed to be screened adequately enough that they are not complete nonsense. So I think this question is on-topic. I have to admit I can't follow that paper either, although I haven't tried that hard.  
> **username_2**: @Turkistany, as for your last question, if this article presented any real new insight into the P vs NP question, it would almost certainly have appeared in a more prestigious publication than SIGACT News.  
> **username_0**: Thanks Peter for clarifying it. My gut feeling tells me there is something original in this paper. I could be wrong.  

---

## 0 answers

