# What makes it so difficult to prove P =/≠ NP? — The subset sum issue [closed]

I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to prove that P = NP.

Let's take the subset sum problem, which is NP-complete. It says that given a set such as $\{-7, -3, -2, 5, 8\}$, we're able to find out if there exists a subset of this set summing to zero, within exponential time (and obviously check a solution, for instance $\{-3, -2, 5\}$ within polynomial time).

So if someone finds an polynomial-time algorithm for this task, he'll show that P = NP, right?

EDIT: I removed:

Assuming, that opinions whether P = NP or P ≠ NP amongst computer scientists are about 1:1 (this site claims that they're ~ 52% and ~44% respectively)...

As the guys noticed in comments, it's wrong. I should say the proven cases are like 1:1.

Okay, so it gets more intuitive now. I mean, P ≠ NP actually seems to be 'more likely now':

However, assuming that there are still, say, 5-10% of formally educated people who believes that P = NP and the cited problem is not, say, the most complex one, how is that even possible that no one of them had found a polynomial-time algorithm yet OR (maybe more likely?) no one of their opponents proved that there's no such an algorithm? Or, does it also mean that (in terms of those people's opinions, again) the 'chances' of there being such an algorithm are like 1:1, too?

From my (maybe naive) point of view, the subset sum problem seems so simple to crack – at least for advanced computer scientists.

As you're probably aware of, searching in the Net would not help me much as I just can't deeper into this problem. I've got no such mathematical knowledge to even comprehend it more.

• I would be very much surprised if the ratio was 1:1, I would expect that more than 90% of formally educated people assume $P \neq NP$. The reason no one has proved either result despite what is probably millions of cumulated hours of effort by now is the same reason mathematical problems sometimes remain open for hundreds of years: they're hard. One example of a problem that is very easy to understand (a fifth-grader will understand what the problem is) but hasn't been solved since its being stated for the first time more than half a century ago is the Collatz Conjecture. – G. Bach Feb 10 '14 at 0:20
• I'm not sure which site claims that 52% of computer scientists believe that P=NP and 44% that P!=NP but that claim is way off: by far the majority believe that P!=NP. Other than that, I can't work out what you're asking. Yes, giving a single polytime algorithm for an NP-complete problem would show P=NP. Beyond that, what are you asking? – David Richerby Feb 10 '14 at 0:20
• @DavidRicherby Sounds to me like somnock is asking "how come no one has figured this out yet, doesn't seem all that hard". – G. Bach Feb 10 '14 at 0:21
• @G.Bach Simply put, that's what I'm asking for. It's a question about intuition or about what's against intuition. – somnock Feb 10 '14 at 0:39
• Please try to edit your question to make it self-contained. As it stands, I can't tell what you are asking. Don't use "EDIT: removed..." stuff, because then it's hard to tell what you are asking. Stick to one question per one question. Is your question "So if someone finds an polynomial-time algorithm for this task, he'll show that P = NP, right?" If so, all the rest of the question seems irrelevant and can be removed. Moreover, that question is answered in standard resources and is not a good fit for this site. We expect you to do research on your own first. – D.W. Feb 10 '14 at 3:20

Many simple-seeming problems turn out to have solutions that are extremely complicated and deep. That's not a bad thing, in fact it's what keeps mathematics interesting. One of the best known examples is Fermat's Last Theorem, which states that the equation $x^n+y^n=z^n$ has no solution in positive integers $x, y, z$ whenever $n\ge 3$. One could hardly ask for a simpler problem, but despite the efforts of some of the brightest mathematicians it remained unsolved for 358 years! On the plus side, three centuries of trying (and failing) to prove Fermat's Last Theorem led to the development of a lot of what's known as algebraic number theory.