Ask HN: Feedback requested for an argument about P =/= NP

An argument that P != NP

1) Multiplication problems (ab, a AND b) are less computationally expensive than addition problems (a+b) by a factor of about 2.

2) NP problems can have in the worst case scenario somewhere in the vicinity of N^K OR operations.

3) P problems have OR operations on the order of NK operations.

4) The increase of AND problems as P --> NP scales linearly in terms of increased computational cost by (1) so we mostly consider the increase of cost due to OR problems as P --> NP.

5) The cost of NP diverges rapidly from P as the number of addition problems (OR operations) increases.

6) By (5) whereas muliplication problems (AND operations) scale linearly as P --> NP, this does not occur for OR operations. An N-SAT problem with many OR operators will always be more difficult than a problem with say N AND gates.

7) Because of the diverging cost of OR as P --> NP, NP cannot be reduced into P, as that would put OR and AND operations on the same footing which cannot be done by (1).

8) As by (7) NP does not reduce to P, P != NP.

Justification of (1) that OR is more expensive than AND:

The problem 2 * 3 is solved by taking pointer p and increasing it by length p, that is to say, moving p from pointing at memory block 3 and moving it down 3 blocks to point at memory block 6.

The problem 2 + 3 is solved by adding a pointer p1, and adding this to p, such that p + p1 gives a state in which p1 is pointed at memory block 5.

The second operation (2 + 3) is more expensive than the first operation (2*3) because in the second one we needed two pointers, p and p1, whereas in the first we only had the one pointer, p.

Thus OR problems (addition operations) need in general more pointers to solve than AND problems (multiplication operations) which translates into being computationally more expensive.