Categories
Uncategorised

P!=NP

True set is a set where all of the members can be represented by at least one relation of any other two members in the same set. Such a relation is called self-relation.

Rational numbers, Q is a true set, because we can define any rational number with it’s direct relation to at least two other rational numbers. A true set is a dimension.

For example, QxQ set which defines a coordinate plane with rational numbers is not a true set, since we cannot represent a value Y in y axis, using two values X1 and X2 on the x axis.

For this, Real Numbers is not a true set. Since the very definition of pi is defined on QxQ set, and it cannot be shown by at least one relation of any other two members in the same set.

Axiom: Any self-relation has computational complexity of O(1).

Example: 3+5 = 8.

Set A is representative for set B if there is at least one injective function defined from A to B.

The least computationally complex injective function from set A to any set is called best representation(BR).

@ operation: @ operation is the transition from an element in a set to another element in another set, using the best representation. A@B is the the transition from an element in A to another element in B. Computation of such transition is represented as O(A@B).

Axiom: If true sets A1 and A2 is not representative in either direction, calculation complexity of the satisfaction of any proposed function from A1 to A2 is equal to or greater than O(C(|A1|+|A2| , 2)), since the only way to compute is by arbitrary combination.

If two sets A1, A2 are representative, true relation of the sets has the calculation complexity O(F(A1->A2)), where F is the best representation and where O(F(A1->A2)) cannot be equal to or more complex then O(C(|A1|+|A2| , 2)).

A problem defines imaginary sets, true relations from those sets to true sets, and defines functions among both imaginary and true sets. Computing a problem is to validating subsets in true and imaginary sets that satisfies all of the functions that problem defines.

The computational complexity in a chain transition A1@A2@…@Ai, O(A1@A2@…@Ai), is lower bounded by the most complex transition O(Aj@Aj+1) for j>=1 & j<i.

If any Aj is not truly related to Aj+1 in A1@A2@…@Ai then O(A1@A2@…@Ai) becomes at least O(C(|Aj|+|Aj+1| , 2)) and Aj@Aj+1 is called a bad representation.

Thesis: If a problem defines an imaginary set with relations to at least two true sets that has no true relation for each other in either way and no imaginary relation between those, computing the problem has to rely on finding an arbitrary combination of elements in those two sets in the best case, which makes the complexity class of the problem not polynomial.

In order to find the lower bound of complexity of the best computing method for a given problem (O(Problem)), first, the true sets in the problem must be written as nodes, then the true relations between the true sets should be mapped among the nodes as directed edges. Then, the sets defined or included in the problem should be written as nodes, and all of the imaginary true relations proposed in the problem should be mapped as directed imaginary edges as well.

The directional path that crosses all of the imaginary sets and true sets that are represented by imaginary sets directly or indirectly with the least complexity defines the lower bound of complexity of computing the given problem.

That path can be transcribed as A1@A2@…@Ai.

If there is no such a path, It can be assumed that, the problem also defines a bad representation edges between sets that are not representative.

However, traversing a bad representation edge multiplies the complexity by at least O(C(|Aj|+|Aj+1| , 2)).

Thus, P!=NP.

Example Problems

0-1 Knapsack

1st dimension, V consist of all possible values.

2nd dimension, W consist of all possible weights.

Problem P1: Find a subset of Index Set (Counting Numbers) where for any element i in that subset, there is a representation in V and W, that is called Vi and Wi and the sum of all Vi’s should be Vj, where the sum of all Wi’s is limited to Wk.

The problem defines a subset and two imaginary true relations shown in orange.

It is impossible to visit every node following the true relations and imaginary relations that are defined.

Bad representations, in red, can be defined in this case. Since Weight set and Value set are both not representative to each other, this transition can happen in both ways, without increasing the lower bound of the complexity any further.

Now we can traverse the imaginary set and every true set that it represents.

So, what that means?

While computing the knapsack problem, since the maximum value is limited by a weight value, each subset of the Value set has to be transitioned to weight set by bad representation to be validated by the limitation in that set.

Or every subset of weight set that satisfies the given condition has to be transitioned to the value set to be compared with all possible values they can get so that they can be validated in the condition defined in Value Set (maximization).

By the definition of Weight and Value sets, there is no true relation.

A bad representation has the complexity of O(C(|W|+|V| , 2)) for each transition.

The problem does not define a function between Weight set and Value set, thus bad representation makes:

O(P1) != P.

O(P1) = NP.

Thus, P!=NP.

*drops the mic*

0-1 Knapsack Problem With A Twist

Problem P2: Find a subset of Index Set (Counting Numbers) where for any element i in that subset, there is a representation in V and W, that is called Vi and Wi and the sum of all Vi’s should be the possible maximum where the sum of all Wi’s is limited to Wk and F(Wi)= Vi, where O(F(Wi)) is calculated in polynomial complexity.

This means, F can be exploited in computation to calculate the satisfactory subset, without resorting to a bad representation. O(P2) becomes O(F), since F is calculated in polynomial complexity, O(P2) = P.

Such a function would define the value through weight, which is in case of Gold and other pure materials.

Leave a Reply

Your email address will not be published. Required fields are marked *